坑点极多的一道bfs好题！
#include#include #include #include #include using namespace std;//Mystery_Sky//#define INF 0x3f3f3f3fconst int M = 100;struct node{ int x, y, step, dirt, turn;//dirt取值为1， 2， 3， 4时别表示东，西，南，北。 node (int xx, int yy, int ss, int dd, int tt) : x(xx), y(yy), step(ss), dirt(dd), turn(tt){}};queue q;int n, m, ans, x1, x2, y1, y2;char to;int dis[M][M], map[M][M];bool vis[M][M];inline void bfs(int x1, int y1, int x2, int y2, char to){ int drt; if(to == 'E') drt = 1; else if(to == 'W') drt = 2; else if(to == 'S') drt = 3; else drt = 4; q.push(node(x1, y1, 0, drt, 0)); while(!q.empty()) { node top = q.front(); q.pop(); int dx, dy; for(int i = 1; i <= 5; i++) {//i=4表示左转， i=5表示右转 if(i != 4 && i != 5) { drt = top.dirt; if(drt == 1) { dx = top.x; dy = top.y + i; } else if(drt == 2) { dx = top.x; dy = top.y - i; } else if(drt == 3) { dx = top.x + i; dy = top.y; } else { dx = top.x - i; dy = top.y; } if(map[dx][dy] == 1) i = 3; if(dx <= 0 || dy <= 0 || dx > n || dy > n) { i = 3; continue; } if(vis[dx][dy]) { continue; } if(dx == x2 && dy == y2) { dis[x2][y2] = top.step + 1; return; } dis[dx][dy] = min(top.step + 1, dis[dx][dy]); vis[dx][dy] = 1; q.push(node(dx, dy, top.step+1, drt, 0)); } else if(i == 4){ int t = top.turn; if(t > 2) continue; dx = top.x, dy = top.y; drt = top.dirt; if(drt == 1) drt = 4; else if(drt == 2) drt = 3; else if(drt == 3) drt = 1; else drt = 2; dis[dx][dy] = min(top.step + 1, dis[dx][dy]); vis[dx][dy] = 1; q.push(node(dx, dy, top.step + 1, drt, t+1)); } else { int t = top.turn; if(t > 2) continue; dx = top.x, dy = top.y; drt = top.dirt; if(drt == 1) drt = 3; else if(drt == 2) drt = 4; else if(drt == 3) drt = 2; else drt = 1; dis[dx][dy] = min(top.step + 1, dis[dx][dy]); vis[dx][dy] = 1; q.push(node(dx, dy, top.step + 1, drt, t+1)); } } } return;}int main() { int a; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf("%d", &a); if(a == 1) { vis[i][j] = vis[i][j+1] = vis[i+1][j] = vis[i+1][j+1] = 1; map[i][j] = map[i][j+1] = map[i+1][j] = map[i+1][j+1] = 1; } } n++, m++; for(int i = 1; i <= m; i++) vis[1][i] = vis[n][i] = 1; for(int i = 1; i <= n; i++) vis[i][1] = vis[i][m] = 1; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); getchar(); x1++, x2++, y1++, y2++; scanf("%c", &to); memset(dis, INF, sizeof(dis)); if(vis[x1][y1] || vis[x2][y2]) return 0 * printf("-1\n"); if(x1 == x2 && y1 == y2) return 0 * printf("0\n"); bfs(x1, y1, x2, y2, to);// for(int i = 1; i <= n; i++){// for(int j = 1; j <= m; j++){// if(dis[i][j] == INF) printf("-1 ");// else printf("%d ", dis[i][j]);// }// printf("\n");// } if(dis[x2][y2] == INF) printf("-1\n"); else printf("%d\n", dis[x2][y2]); return 0;}