一道又简单又难的BFS题
这道题是个人看上去就知道要BFS。
随手写了个BFS，算样例的答案是7？
翻题解发现：障碍点不能跳过！
改过来，终于是12了。交上去，MLE！
显然会有很多状态是重复的，我们可以开一个三维的布尔数组来判重，很傻瓜的操作。
应该改完了，交上去，还有TLE？
哦，我还添加少了vis标记，再慢慢地复制粘贴。
最后的一个错的点居然WA了？
看讨论区的dalao说要先转向再走路，试着改了一下，就对了。。。
这道题给我的提醒：
玩BFS一定要注意判重！
连续的走如果可以一次性完成，但也不能跳过任何的障碍！
代码：
#include#include #include const int maxn = 55;int a[maxn][maxn];bool vis[maxn][maxn][5];struct Nodes{ int x, y; char dir; int dis;};int n, m;int sx, sy, tx, ty;int id(char x){ if(x == 'N') return 1; else if(x == 'S') return 2; else if(x == 'W') return 3; else if(x == 'E') return 4; else return 0;}bool check(int x, int y, int idx){ bool flag1 = (x >= 1 && x < n && y >= 1 && y < m); bool flag2 = (a[x][y] || a[x + 1][y] || a[x][y + 1] || a[x + 1][y + 1]); bool flag3 = vis[x][y][idx]; if(flag1 && !flag2 && !flag3) return true; return false;}int bfs(int sx, int sy, char dir){ std::queue q; if(!check(sx, sy, id(dir))) return -1; q.push((Nodes){sx, sy, dir, 0}); vis[sx][sy][id(dir)] = true; while(!q.empty()) { Nodes node = q.front(); q.pop(); int x = node.x, y = node.y; char dir = node.dir; int dis = node.dis; if(x == tx && y == ty) { return dis; } if(dir == 'N') { if(!vis[x][y][id('E')]) { q.push((Nodes){x, y, 'E', dis + 1}); vis[x][y][id('E')] = true; } if(!vis[x][y][id('W')]) { q.push((Nodes){x, y, 'W', dis + 1}); vis[x][y][id('W')] = true; } for(int i = 1; i <= 3; i++) { int nx = x - i, ny = y; if(check(nx, ny, id(dir))) { q.push((Nodes){nx, ny, dir, dis + 1}); vis[nx][ny][id(dir)] = true; } else break; } } else if(dir == 'E') { if(!vis[x][y][id('N')]) { q.push((Nodes){x, y, 'N', dis + 1}); vis[x][y][id('N')] = true; } if(!vis[x][y][id('S')]) { q.push((Nodes){x, y, 'S', dis + 1}); vis[x][y][id('S')] = true; } for(int i = 1; i <= 3; i++) { int nx = x, ny = y + i; if(check(nx, ny, id(dir))) { q.push((Nodes){nx, ny, dir, dis + 1}); vis[nx][ny][id(dir)] = true; } else break; } } else if(dir == 'S') { if(!vis[x][y][id('E')]) { q.push((Nodes){x, y, 'E', dis + 1}); vis[x][y][id('E')] = true; } if(!vis[x][y][id('W')]) { q.push((Nodes){x, y, 'W', dis + 1}); vis[x][y][id('W')] = true; } for(int i = 1; i <= 3; i++) { int nx = x + i, ny = y; if(check(nx, ny, id(dir))) { q.push((Nodes){nx, ny, dir, dis + 1}); vis[nx][ny][id(dir)] = true; } else break; } } else if(dir == 'W') { if(!vis[x][y][id('N')]) { q.push((Nodes){x, y, 'N', dis + 1}); vis[x][y][id('N')] = true; } if(!vis[x][y][id('S')]) { q.push((Nodes){x, y, 'S', dis + 1}); vis[x][y][id('S')] = true; } for(int i = 1; i <= 3; i++) { int nx = x, ny = y - i; if(check(nx, ny, id(dir))) { q.push((Nodes){nx, ny, dir, dis + 1}); vis[nx][ny][id(dir)] = true; } else break; } } } return -1;}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &a[i][j]); char dir; scanf("%d%d%d%d %c", &sx, &sy, &tx, &ty, &dir); printf("%d\n", bfs(sx, sy, dir)); return 0;}