@[_KMnO4_](/user/1211186) 不要用 memset,建议输入了地图之后根据大小清空
by MarsTraveller @ 2024-03-11 20:30:53
@[MarsTraveller](/user/735797) 又WA了
```cpp
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e3 + 10, dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1};
queue<int> qx, qy;
bool vis[maxn][maxn];
char str[maxn][maxn], last[maxn][maxn];
int T, n, m, nx, ny, ux, uy, dis[maxn][maxn];
void print(int x, int y) {
if (last[x][y] == 'N') return ;
if (last[x][y] == 'R') print(x, y - 1);
if (last[x][y] == 'L') print(x, y + 1);
if (last[x][y] == 'U') print(x + 1, y);
if (last[x][y] == 'D') print(x - 1, y);
printf("%c", last[x][y]);
return ;
}
void Bfs(int sx, int sy) {
qx.push(sx), qy.push(sy);
dis[sx][sy] = 0;
vis[sx][sy] = true;
last[sx][sy] = 'N';
while (qx.size()) {
ux = qx.front();
uy = qy.front();
qx.pop(), qy.pop();
for (int i = 1; i <= 4; i++) {
nx = ux + dx[i - 1];
ny = uy + dy[i - 1];
if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] || str[nx][ny] == str[ux][uy]) continue;
vis[nx][ny] = true;
dis[nx][ny] = dis[ux][uy] + 1;
if (i == 1) last[nx][ny] = 'R';
if (i == 2) last[nx][ny] = 'L';
if (i == 3) last[nx][ny] = 'U';
if (i == 4) last[nx][ny] = 'D';
qx.push(nx);
qy.push(ny);
}
}
return ;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf(" %s", str + i);
for (int j = 1; j <= m; j++) {
dis[i][j] = -1;
vis[i][j] = false;
}
}
Bfs(1, 1);
if (~dis[n][m]) {
printf("%d\n", dis[n][m]);
print(n, m);
putchar(10);
} else puts("-1");
}
return 0;
}
```
by _KMnO4_ @ 2024-03-11 20:38:09
@[_KMnO4_](/user/1211186) 您输入假了:
```cpp
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch = getchar();
while(ch != '0' && ch != '1')
{
ch = getchar();
}
str[i][j] = ch-'0';
dis[i][j] = -1;
vis[i][j] = false;
}
}
```
by MarsTraveller @ 2024-03-11 21:01:36
@[_KMnO4_](/user/1211186) 建议编译选项把 Warning 提示也看一下
by MarsTraveller @ 2024-03-11 21:02:17
@[MarsTraveller](/user/735797) 抱歉,是我脑残了,小号已关注
by Lian_lele @ 2024-03-11 21:34:03