输入输出样例 输入 #1复制 9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 7 2 2 7 S 输出 #1复制 12

题意理解

机器人必须在最短的时间内把物品搬运到指定的地方 每个指令所需要的时间为1秒 请你计算一下机器人完成任务所需的最少时间 分别为起始点和目标点左上角网格的行与列

简单来说，我们需要从一个点移动到另外一个点，正常来说这是非常简单的事情； 这题的特点是移动的过程需要转向； 另外加就是机器人移动的过程具有体积； 另外就是障碍物也是有体积的。由于数据量并不太大，所以可能暂时不需要记忆化搜索。

搜索过程有一个关键是如何去除重复搜索的问题，就是这一题中如何标记才能防止反复搜索。

总结目录

1 如何解决本题的去除重复搜索问题 2 本题的建图过程，如何将格子图建立为点图 3 格子图变为点图后，搜索范围的确定过程，如何判定越界 4 本题复杂的逻辑，如何利用对象的思想进行编程，如何抽象状态

1 如何去除重复搜索

这题是要我们求一个最少的时间去到固定点的时间。对于这题的搜索，我们的状态至少需要包括位置row,col,以及当前的方向dir。那么除此之外我们还需不需要加上其他的状态？如果我从A->B后，我应该如何标记，才能把B->A的那个方案给剪枝掉呢？

在这一题中，使用了类似于dijkstra的最短路算法的方法。在dijkstra中，有一个距离数组dist[]，只有当 当前结点搜索能够更新最短距离的情况下，才允许其入列，入列后更新该结点周围的dist[]，利用这种方法，如果从A->B，再从B->A的话，距离一定是更长的，那么这种搜索的方案就会被排除掉！

类似的，在这题中，有一个距离矩阵timemark[][],这个矩阵用来记录能够到达当前结点的最短的时间，其实就类似于单源最短路径的算法。然后就是不断的搜索，只有当到达这个结点的时间是更优的情况下，才将这个结点看作是有意义的状态结点，并把它加入队列q。 那么为什么这个算法是正确的，为什么即使前面不好，后面也不会更好，这个原因类似于dijkstra的推理，这里就不再进行赘述了。

建图过程

本题中，需要将格子图重建为点图。这里对这种图扩散的总体思路做一个总结。格子图建为点图，需要先 把格子生成一定数量的点，然后再根据不同格子的位置把对应的点给染色为不同的数值。这里格子图的维度为N,M，那么对应点图就是n=N+1,m=M+1;染色的时候只需要染色 [row,col],[row+1,col+1],[row+1,col],[row,col+1] 即可。同理，如果是3X3的，也一样可以进行对应的映射染色。但是总体的流程都是 生成点阵，再去染不同的点。

搜索范围的确定

本题中有一个细节，就是机器人是有体积的，在格子图变为点图之后，机器人可以站的点的范围一定是row>=2,row<=n-1;col>=2,col<=m-1。 因此，这里不再是row<1,row>n了，也就是第1行和第n行都不再可行了。

复杂逻辑与面向对象

每个node的状态包含了row,col,time,dir。每次转向的时候，会更新对应的状态。因此我们写了turnright,turnleft等函数来对状态进行修改。

在pace（）中需要判断整条路径上都可行，才是可行的。因为可以走多步，因此可能最终位置是可行的，但是路程上的方法是不可行的。

为了标定对应的方向，使用了map<char,int>来匹配。

一些debug的过程

对于a++的使用需要更谨慎一点。有时候想求+1的话，最好还是把数值+1，a++的话你可能不知道这个数值到底是返回什么。

换句话说,a++命令的返回你可能不确定是什么；但是a+1的运行值是很明显的一个值了。

另外就是int b[4]; b[i++];的访问就是先访问b[i],再i++;

Turnback函数的时间为+2；

越界的定义

重复搜索的去除

代码

#include<iostream> #include<map> #include<queue> #include<climits> #include<algorithm> #define maxsize 55 using namespace std; int inimat[maxsize][maxsize]; int mat[maxsize][maxsize]; int timemark[maxsize][maxsize]; int dir[][4] = { {0,1},{1,0},{0,-1},{-1,0} }; map<char, int> dir_vec = { {'E',0},{'S',1},{'W',2},{'N',3} }; char dir_hash[4] = { 'E','S','W','N' }; int N, M;//原始输入 int n, m;//点图对应的维度 void GridToPointMap() { //将格子图转换为点图 //先生成，生成对应数量的点 n = N + 1; m = M + 1; //染色，根据格子图将对应颜色的点进行染色 for (int row = 1; row <= n; row++) { for (int col = 1; col <= m; col++) { if (inimat[row][col] == 1) { mat[row][col] = 1; mat[row + 1][col + 1] = 1; mat[row][col + 1] = 1; mat[row + 1][col] = 1; } } } } struct node { //状态结点定义 int row; int col; char dir; int time; }; void TurnRight(node& obj) { obj.time++; char inidir = obj.dir; if (dir_vec[inidir] < 3) { obj.dir = dir_hash[dir_vec[inidir]+1];//这个+1写成++的话也会错 } else { obj.dir = dir_hash[0]; } } void TurnLeft(node& obj) { obj.time++; char inidir = obj.dir; if (dir_vec[inidir] > 0) { obj.dir = dir_hash[dir_vec[inidir]-1]; } else { obj.dir = dir_hash[3]; } } void TurnBack(node& obj) { obj.time=obj.time+2;//这里向后转时间花费是2秒 char inidir = obj.dir; switch (inidir) { case 'E': obj.dir = 'W'; break; case'W': obj.dir = 'E'; break; case'N': obj.dir = 'S'; break; case'S': obj.dir = 'N'; break; default: break; } } void turndir(node& obj, int dir_index) { //对obj对象进行方向调整，其中dir_index作为循环接口调用函数 switch (dir_index) { case 0: break; case 1: TurnRight(obj); break; case 2: TurnLeft(obj); break; case 3: TurnBack(obj); break; default: break; } } bool pace(node obj, int step) { //obj向当前方向行走step，在该过程中没有障碍 bool res = true; int currow = obj.row; int curcol = obj.col; int rowinc = dir[dir_vec[obj.dir]][0]; int colinc = dir[dir_vec[obj.dir]][1]; for (int i = 1; i <= step; i++) { int nextrow = currow + rowinc*i; int nextcol = curcol + colinc*i; if (nextrow>n-1||nextrow<2||nextcol>m-1||nextcol<2||mat[nextrow][nextcol] == 1) {//这个越界判别容易错 res = false;//越界+障碍判断，路径上只要有一步有阻碍，就跳出循环 break; } } return res; } node GoPoint(node obj, int step) { node res = obj; res.time++; res.row = res.row + dir[dir_vec[res.dir]][0] * step; res.col = res.col + dir[dir_vec[res.dir]][1] * step; return res; } int bfs(int srow, int scol, int trow, int tcol, char begindir) { if (srow == trow&&scol == tcol)return 0; node start; start.row = srow; start.col = scol; start.dir = begindir; start.time = 0; queue<node> q; q.push(start); while (!q.empty()) { node tmp = q.front(); q.pop(); //注意，这里不建议直接跳出直接返回结点的时间，因为当前结点虽然能够搜索到，但是并不一定是最小的 //如果要查找最小的时间，还是应该去搜索timemark[][]矩阵里面的结果！ for (int i = 0; i < 4; i++) { node tmp2 = tmp; turndir(tmp2, i);//转向不同方向,转完方向后时间已经计算完转向时间 for (int step = 1; step <= 3; step++) { if (pace(tmp2, step)) {//如果该路径可以走 node tmp3=GoPoint(tmp2, step); if (tmp3.time < timemark[tmp3.row][tmp3.col]) {//如果这一步可以更新时间 timemark[tmp3.row][tmp3.col] = tmp3.time;//更新时间 q.push(tmp3);//入队 } } } } } if (timemark[trow][tcol] == INT_MAX) { return -1;//到达不了就是INT_MAX } else { return timemark[trow][tcol]; } } int main() { fill(timemark[0], timemark[0] + maxsize*maxsize, INT_MAX); cin >> N >> M; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> inimat[i][j];//原始地图输入 } } int s_row, s_col, t_row, t_col; char begin_dir; cin >> s_row >> s_col >> t_row >> t_col >> begin_dir; GridToPointMap();//格子图转换为点图 cout<<bfs(s_row+1, s_col+1, t_row+1, t_col+1, begin_dir);//起点是点，输入的是格子，因此要+1 return 0; }