3 solutions
-
1
不要给差评啊，有点素质好不好？具体在注释里，细节很多，注意看看（少写一个细节貌似就会挂分了）
#include <iostream> #include <queue> #include <cstring> using namespace std; const int N = 500; int n, m, vis[N + 5][N + 5][3], ans = -1; char a[N + 5][N + 5]; // vis表示这个点有没有来过，a就是这个矩形 // ans设为 -1，最后如果无法达到目标单元格就输出 "Impossible" struct State { int x, y, sta, ste; // x，y（坐标），state（状态），step（步数） // sta 共3种情况：0：直立 1: 横躺 2: 竖躺 } st, ed; // 起点与终点 void bfs() { queue<State> q; q.push(st); while (!q.empty()) { int x = q.front().x, y = q.front().y; // 记录坐标 int s = q.front().sta, step = q.front().ste; // 记录状态与当前步数 q.pop(); if (x == ed.x && y == ed.y && s == ed.sta) // 到终点了 { ans = step; return; } if (a[x][y] == 'E' && s == 0) continue; // 在“易碎单元格”且是直立的 if (a[x][y] == '#' || a[x][y + 1] == '#' && s == 1) continue; //越界了 if (a[x + 1][y] == '#' && s == 2) continue; //越界了 if (vis[x][y][s]) continue; //同一状态下走过了 vis[x][y][s] = 1; //标记走过了 if (s == 0) //直立时 { q.push({x, y - 2, 1, step + 1}); q.push({x, y + 1, 1, step + 1}); q.push({x - 2, y, 2, step + 1}); q.push({x + 1, y, 2, step + 1}); } else if (s == 1) //横躺时 { q.push({x, y - 1, 0, step + 1}); q.push({x, y + 2, 0, step + 1}); q.push({x - 1, y, 1, step + 1}); q.push({x + 1, y, 1, step + 1}); } else //竖躺时 { q.push({x, y - 1, 2, step + 1}); q.push({x, y + 1, 2, step + 1}); q.push({x - 1, y, 0, step + 1}); q.push({x + 2, y, 0, step + 1}); } } } int main() { while (cin >> n >> m && n && m) { for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> a[i][j]; bool flag = false; // 找起点 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (a[i][j] == 'X') { if (a[i][j + 1] == 'X') st.sta = 1; //起点是横躺状态 else if (a[i + 1][j] == 'X') st.sta = 2; //起点是竖躺状态 else st.sta = 0; //起点是直立状态 st.x = i, st.y = j; flag = true; break; } } if (flag) break; } flag = false; // 找终点 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (a[i][j] == 'O') { if (a[i][j + 1] == 'O') ed.sta = 1; //终点是横躺状态 else if (a[i + 1][j] =='O') ed.sta = 2; //终点是竖躺状态 else ed.sta = 0; //终点是直立状态 ed.x = i, ed.y = j; flag = true; break; } } if (flag) break; } bfs(); if (ans == -1) cout << "Impossible" << endl; else cout << ans << endl; memset(vis, 0, sizeof(vis)); ans = -1; } return 0; } -
0
C23huangminzhe LV 6 @ 2025-3-7 20:38:05
题意
就是个模拟，题意很清晰了
思路
不难发现，这就是个升级版迷宫，加入了方块的多种状态，我们只需升级一下方向数组就行了（L10~L18）。
这边看到很多人都把判断终点状态的代码加上了，其实不用，题目已经说了终点只可能是一个格子，所以不用判断。
~~最重要的一点（对我来说），~~开 O2 了记得初始化变量，不管是局部还是全局。
代码
#include <bits/stdc++.h> using namespace std; struct blk{ int x,y,pt,stp; }; const int N = 5e2 + 5,INF = 0x7fffffff; int n,m; char a[N][N]; int spt,sx,sy,mn; int dx[5][5] = {{-2,1,0,0}, {-1,1,0,0}, {-1,2,0,0}}, dy[5][5] = {{0,0,-2,1}, {0,0,-1,2}, {0,0,-1,1}}, dpt[5][5] = {{2,2,1,1}, {1,1,0,0}, {0,0,2,2}}; int f[N][N][5]; void bfs(int sx,int sy,int spt){ queue<blk> q; q.push({sx,sy,spt,0}); while (!q.empty()){ int x = q.front().x,y = q.front().y,pt = q.front().pt,stp = q.front().stp; q.pop(); if (a[x][y] == 'O' && !pt){ mn = stp; return; } if (a[x][y] == '#' || !pt && a[x][y] == 'E' || pt == 1 && a[x][y + 1] == '#' || pt == 2 && a[x + 1][y] == '#' || f[x][y][pt] <= stp) continue; // 记得加等于号 // printf("%d %d %d %d\n",x,y,pt,stp); f[x][y][pt] = stp; for (int i = 0;i < 4;i++){ int xi = x + dx[pt][i],yi = y + dy[pt][i],pti = dpt[pt][i]; q.push({xi,yi,pti,stp + 1}); } } } int main(int argc, char **argv){ cin >> n >> m; while (n || m){ mn = INF; memset(f,0x7f,sizeof f); for (int i = 1;i <= n;i++){ for (int j = 1;j <= m;j++){ cin >> a[i][j]; if (a[i][j] == 'X'){ if (a[i][j - 1] == 'X') sx = i,sy = j - 1,spt = 1; else if (a[i - 1][j] == 'X') sx = i - 1,sy = j,spt = 2; else sx = i,sy = j,spt = 0; // 开O2的把`spt=0`加上 } } } bfs(sx,sy,spt); if (mn == INF) cout << "Impossible\n"; else printf("%d\n",mn); cin >> n >> m; } return 0; } -
-2
#include <iostream> #include <queue> #include <cstring> using namespace std; const int N = 500; int n, m, vis[N + 5][N + 5][3], ans = -1; char a[N + 5][N + 5]; // vis表示这个点有没有来过，a就是这个矩形 // ans设为 -1，最后如果无法达到目标单元格就输出 "Impossible" struct State { int x, y, sta, ste; // x，y（坐标），state（状态），step（步数） // sta 共3种情况：0：直立 1: 横躺 2: 竖躺 } st, ed; // 起点与终点 void bfs() { queue<State> q; q.push(st); while (!q.empty()) { int x = q.front().x, y = q.front().y; // 记录坐标 int s = q.front().sta, step = q.front().ste; // 记录状态与当前步数 q.pop(); if (x == ed.x && y == ed.y && s == ed.sta) // 到终点了 { ans = step; return; } if (a[x][y] == 'E' && s == 0) continue; // 在“易碎单元格”且是直立的 if (a[x][y] == '#' || a[x][y + 1] == '#' && s == 1) continue; //越界了 if (a[x + 1][y] == '#' && s == 2) continue; //越界了 if (vis[x][y][s]) continue; //同一状态下走过了 vis[x][y][s] = 1; //标记走过了 if (s == 0) //直立时 { q.push({x, y - 2, 1, step + 1}); q.push({x, y + 1, 1, step + 1}); q.push({x - 2, y, 2, step + 1}); q.push({x + 1, y, 2, step + 1}); } else if (s == 1) //横躺时 { q.push({x, y - 1, 0, step + 1}); q.push({x, y + 2, 0, step + 1}); q.push({x - 1, y, 1, step + 1}); q.push({x + 1, y, 1, step + 1}); } else //竖躺时 { q.push({x, y - 1, 2, step + 1}); q.push({x, y + 1, 2, step + 1}); q.push({x - 1, y, 0, step + 1}); q.push({x + 2, y, 0, step + 1}); } } } int main() { while (cin >> n >> m && n && m) { for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> a[i][j]; bool flag = false; // 找起点 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (a[i][j] == 'X') { if (a[i][j + 1] == 'X') st.sta = 1; //起点是横躺状态 else if (a[i + 1][j] == 'X') st.sta = 2; //起点是竖躺状态 else st.sta = 0; //起点是直立状态 st.x = i, st.y = j; flag = true; break; } } if (flag) break; } flag = false; // 找终点 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (a[i][j] == 'O') { if (a[i][j + 1] == 'O') ed.sta = 1; //终点是横躺状态 else if (a[i + 1][j] =='O') ed.sta = 2; //终点是竖躺状态 else ed.sta = 0; //终点是直立状态 ed.x = i, ed.y = j; flag = true; break; } } if (flag) break; } bfs(); if (ans == -1) cout << "Impossible" << endl; else cout << ans << endl; memset(vis, 0, sizeof(vis)); ans = -1; } return 0; }
C25liangwenjing
LV 5
@ 2025-3-7 20:17:35
- 1
