所以在读完输入键一个图后，可以再创建一个简化版的图，mini map。它将原图中每四个格点当做一个点，而机器人只走这四个格子的中心，一旦一个四方格中有一个障碍，那么这个四方格认为不可走。这样一来机器人移动、机器人半径、单个方格障碍物问题就简化成了最常见的情况：在一个图上的点避开障碍物到达另一个点的最短路。（这中简化和机器人在原图上的移动是等价的，可以模拟一下）。
以下是这部分处理代码：
for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { cin >> graph[i][j]; } } int p = 0,q = 0; for(int i = 0; i < n-1; ++i) { q = 0; for(int j = 0; j < m-1; ++j) { if(graph[i][j] || graph[i][j+1] || graph[i+1][j] || graph[i+1][j+1]) mini[p][q] = 1;//标记为障碍，否则为 0 表示可达 q++; } p++; }建出了图，现在考虑状态的转移。此题中，每个节点可以有三种转移情况，向左转，向右转，移动。
每种情况耗时为 1（可以认为是距离，权重）。关于转向问题，可以定义一个方向数组，按顺时针顺序给出北东南西，然后无论朝向那个方位，向左转就是数组索引减一，向右转就是加一，检索方向数组获得新的方位。完成一次转向后，就完成了一次状态转移，将新的节点入队列，这个新的节点在下一次被取出考虑进行转移状态时，他的当前方向就是移动的方向。
宏和数据结构：
#define MAX 50 #define DIR 4 #define N 0 #define E 1 #define S 2 #define W 3 struct Node { int x,y; int step = 0; int d; Node (int x,int y,int step,int dir) { this->x = x,this->y = y,this->step = step,this->d = dir; } // Node () {} // int pre = 0; // int loc = 0; }; int graph[MAX + 1][MAX + 1]; int mini[MAX + 1][MAX + 1]; //mini graph int vis[MAX + 1][MAX + 1][DIR]; // N E S W int dx[] = {-1,0, 1, 0}; int dy[] = {0, 1, 0,-1}; int n,m;BFS 代码：
Node bfs(int sx,int sy,int tx,int ty,int dir) { queue<Node> q; Node start = Node(sx,sy,0,dir); q.push(start); // path[pi++] = start; vis[sx][sy][dir] = 1; while(!q.empty()) { Node u = q.front(); q.pop(); if(u.x == tx && u.y == ty) return u; //尝试向左转 if(!vis[u.x][u.y][(u.d-1+DIR)%DIR]) { vis[u.x][u.y][(u.d-1+DIR)%DIR] = 1; Node nu = Node(u.x,u.y,u.step+1,(u.d-1+DIR)%DIR); // nu.pre = u.loc; //记录路径信息 // nu.loc = pi; // path[pi++] = nu; q.push(nu); } //尝试向右转 if(!vis[u.x][u.y][(u.d+1)%DIR]) { vis[u.x][u.y][(u.d+1)%DIR] = 1; Node nu = Node(u.x,u.y,u.step+1,(u.d+1)%DIR); // nu.pre = u.loc; // nu.loc = pi; // path[pi++] = nu; q.push(nu); } //尝试移动 creep，walk，run for(int i = 1; i <= 3; ++i) { Node nu = Node(u.x,u.y,u.step+1,u.d); //判断是是否有障碍物。只要有一个，就不必移动了。 bool isok = true; for(int j = 0; j < i; ++j) { if(mini[nu.x+dx[u.d]*j][nu.y+dy[u.d]*j]) { isok = false; break; } } if(isok == false) break; nu.x += dx[u.d] * i; nu.y += dy[u.d] * i; if(inrange(nu) && !vis[nu.x][nu.y][nu.d]) { vis[nu.x][nu.y][nu.d] = 1; // nu.pre = u.loc; // nu.loc = pi; // path[pi++] = nu; q.push(nu); } } } return Node(-1,-1,-1,-1); }其中注释代码是用来记录最短路的路径信息。在这里是我用来测试程序的。
在调试的时候遇到一个 bug 花了我几个小时，机器人移动方式有 creep，walk，run，分别移动 1 、2 、3 步，在移动步数大于 1 时，不能只判断目标节点是否是障碍物，而要判断每一步是否有障碍物。
完整程序：
#include <iostream> #include <algorithm> #include <cstring> #include <stdlib.h> #include <memory.h> #include <queue> using namespace std; #define MAX 50 #define DIR 4 #define N 0 #define E 1 #define S 2 #define W 3 struct Node { int x,y; int step = 0; int d; Node (int x,int y,int step,int dir) { this->x = x,this->y = y,this->step = step,this->d = dir; } // Node () {} // int pre = 0; // int loc = 0; }; int graph[MAX + 1][MAX + 1]; int mini[MAX + 1][MAX + 1]; //mini graph int vis[MAX + 1][MAX + 1][DIR]; // N E S W int dx[] = {-1,0, 1, 0}; int dy[] = {0, 1, 0,-1}; int n,m; // Node path[MAX * MAX + 1]; // int pi = 0; bool inrange(Node nd) { return nd.x >= 0 && nd.x <= n-2 && nd.y >= 0 && nd.y <= m-2; } Node bfs(int sx,int sy,int tx,int ty,int dir) { queue<Node> q; Node start = Node(sx,sy,0,dir); q.push(start); // path[pi++] = start; vis[sx][sy][dir] = 1; while(!q.empty()) { Node u = q.front(); q.pop(); if(u.x == tx && u.y == ty) return u; //尝试向左转 if(!vis[u.x][u.y][(u.d-1+DIR)%DIR]) { vis[u.x][u.y][(u.d-1+DIR)%DIR] = 1; Node nu = Node(u.x,u.y,u.step+1,(u.d-1+DIR)%DIR); // nu.pre = u.loc; //记录路径信息 // nu.loc = pi; // path[pi++] = nu; q.push(nu); } //尝试向右转 if(!vis[u.x][u.y][(u.d+1)%DIR]) { vis[u.x][u.y][(u.d+1)%DIR] = 1; Node nu = Node(u.x,u.y,u.step+1,(u.d+1)%DIR); // nu.pre = u.loc; // nu.loc = pi; // path[pi++] = nu; q.push(nu); } //尝试移动 creep，walk，run for(int i = 1; i <= 3; ++i) { Node nu = Node(u.x,u.y,u.step+1,u.d); ////判断是是否有障碍物。只要有一个，就不必移动了。 bool isok = true; for(int j = 1; j <= i; ++j) { if(mini[nu.x+dx[u.d]*j][nu.y+dy[u.d]*j]) { isok = false; break; } } if(isok == false) break; nu.x += dx[u.d] * i; nu.y += dy[u.d] * i; if(inrange(nu) && !vis[nu.x][nu.y][nu.d]) { vis[nu.x][nu.y][nu.d] = 1; // nu.pre = u.loc; // nu.loc = pi; // path[pi++] = nu; q.push(nu); } } } return Node(-1,-1,-1,-1); } int main(int argc, char const *argv[]) { freopen("/home/skipper/Documents/code/刷题/洛谷 OJ/重启/in.txt","r",stdin); int sx,sy,tx,ty; char dir; cin >> n >> m; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { cin >> graph[i][j]; } } int p = 0,q = 0; for(int i = 0; i < n-1; ++i) { q = 0; for(int j = 0; j < m-1; ++j) { if(graph[i][j] || graph[i][j+1] || graph[i+1][j] || graph[i+1][j+1]) mini[p][q] = 1; q++; } p++; } int d; cin >> sx >> sy >> tx >> ty >> dir; switch(dir) { case 'S': d = S;break; case 'N': d = N;break; case 'E': d = E;break; case 'W': d = W;break; }; //test 查看 mini map // for(int i = 0; i < p; ++i) { // for(int j = 0; j < q; ++j) { // cout << mini[i][j] << " "; // } // cout << endl; // } Node res = bfs(sx-1,sy-1,tx-1,ty-1,d); //输出路径 // int pp = res.loc; // do { // cout << path[pp].x << "," << path[pp].y << endl; // pp = path[pp].pre; // }while(pp); cout << res.step << endl; return 0; }如有错误，欢迎指正评论。