输入输出样例 输入样例#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
思路： 这道题就不是普通的BFS模板题了，因为移动规则并不是上下左右四个方向了。而是有左转，右转，前进1步，前进2步，前进3步五种状态了。同时我们还要记录当前的坐标信息，所以我们需要一个三维数组vis[maxn][maxn][5],一二维表示坐标，第三维表示方向（东南西北），然后我们在进行BFS入队列时候，如果是左转和右转，就更改方向信息，判断新的方向+坐标这个状态是否被访问，若未访问，则入队列。在判断是否前进时，利用一个for循环，s表示前进的步数，judge函数用于判断前进的合法性。利用一个for循环判断走1/2/3步的合法性，如果走1步都不合法，2/3步肯定也不合法，所以可以break中止。再把合法的下一步状态p入队列。 AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<string> #include<map> using namespace std; const int maxn = 55; int g[maxn][maxn]; map<char, int>cimp; //用0-4分别表示四个方向 int n, m, sx, sy, fx, fy; char dir; int vis[maxn][maxn][5]; struct p { int x, y, d,t; //x，y表示坐标 ,d表示方向，t表示到当前状态所需时间 p(int xx, int yy, int dd,int tt) { x = xx; y = yy; d = dd; t = tt; } }; bool judge(int x,int y,int d,int s) { //判断合法性,d表示方向，s表示前进步数 if (d == 0) //根据方向改变坐标 y+=s; else if (d == 1) x+=s; else if (d == 2) y-=s; else x-=s; //要判断x,y x+1,y x,y+1 x+1,y+1 四个点在地图上是否有阻碍，画个图就明白了 if (x > 0 && x < n&&y>0 && y < m && !g[x][y] && !g[x][y + 1] && !g[x + 1][y] && !g[x + 1][y + 1]) { return true; } return false; } void bfs(int x, int y) { if (sx == fx && sy == fy) { //如果起点等于终点，就直接输出0 cout << "0"; return; } cimp['E'] = 0; //0表示向东 cimp['S'] = 1; cimp['W'] = 2; cimp['N'] = 3; queue<p>q; q.push(p(x, y, cimp[dir],0)); while (!q.empty()) { p f = q.front(); q.pop(); int lx = f.x; int ly = f.y; int ld = f.d; int rop = (ld + 1) % 4; //向右转 if (!vis[lx][ly][rop]) { vis[lx][ly][rop] = 1; q.push(p(lx, ly, rop,f.t+1)); } int lop = ld - 1; if (lop < 0) lop = 3; if (!vis[lx][ly][lop]) { //向左转 vis[lx][ly][lop] = 1; q.push(p(lx, ly, lop, f.t + 1)); } for (int s = 1; s <= 3; s++) { if (judge(lx, ly, ld, s)) { //合法性判断 if (ld == 0 && !vis[lx][ly + s][ld]) { //四个方向的判断 if (lx == fx && ly + s == fy) { //返回的判断 cout << f.t + 1; return; } vis[lx][ly + s][ld] = 1; //设置状态访问位 q.push(p(lx, ly + s, ld, f.t + 1)); } else if (ld == 1 && !vis[lx + s][ly][ld]) { if (lx+s== fx && ly == fy) { cout << f.t + 1; return; } vis[lx + s][ly][ld] = 1; q.push(p(lx+s, ly, ld, f.t + 1)); } else if (ld == 2 && !vis[lx][ly-s][ld]) { if (lx == fx && ly-s == fy) { cout << f.t + 1; return; } vis[lx][ly - s][ld] = 1; q.push(p(lx, ly -s, ld, f.t + 1)); } else if (ld == 3 && !vis[lx - s][ly][ld]) { if (lx -s == fx && ly == fy) { cout << f.t + 1; return; } vis[lx - s][ly][ld] = 1; q.push(p(lx-s, ly, ld, f.t + 1)); } } else //这里利用for循环是因为,前进1步是前进2步和3步的子过程，如果走1步都不合法，2/3步肯定也不合法 break; } } cout << "-1"; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <=n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &g[i][j]); } } scanf("%d %d %d %d %c", &sx, &sy, &fx, &fy, &dir); bfs(sx, sy); return 0; }