LemonLeo @ 2023-07-26 19:54:57
cin >> n;
// getchar();
string s;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
cin >> s;
g[i][j] = s[0];
if (s == "A")
sx = i, sy = j;
if (s == "B")
ex = i, ey = j;
}
本地运行结果正确,评测机只有一个测试点AC
for (int i = 1; i <= n; ++i)
{
for (int j = 2; j <= n * 2 + 1; ++j)
{
char ch = getchar();
if (ch == 'A')
sx = i, sy = j / 2;
if (ch == 'B')
ex = i, ey = j / 2;
if (j % 2 == 0)
g[i][j / 2] = ch;
}
getchar();
}
// P1649 [USACO07OCT] Obstacle Course S
// BFS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 110;
struct Node
{
int x, y, dr;
};
char g[maxn][maxn];
int n, sx, sy, ex, ey, ans = 0x3f3f3f3f;
int turn[maxn][maxn][4];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // 上右下左 0123
int bfs()
{
memset(turn, 0x3f, sizeof turn);
queue<Node> q;
for (int i = 0; i < 4; ++i)
{
q.push({sx, sy, i});
turn[sx][sy][i] = 0;
}
while (!q.empty())
{
auto t = q.front();
q.pop();
if (turn[t.x][t.y][t.dr] > ans)
continue;
for (int i = 0; i < 4; ++i)
{
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > n || g[xx][yy] == 'x')
continue;
if (xx == ex && yy == ey)
ans = min(ans, turn[xx][yy][i] + (t.dr == i ? 0 : 1));
if (turn[xx][yy][i] == 0x3f3f3f3f)
{
turn[xx][yy][i] = turn[t.x][t.y][t.dr] + (t.dr == i ? 0 : 1);
q.push({xx, yy, i});
}
else if (turn[xx][yy][i] > turn[t.x][t.y][t.dr] + (t.dr == i ? 0 : 1)) // 允许重复走到同一位置(来的方向不同)
turn[xx][yy][i] = turn[t.x][t.y][t.dr] + (t.dr == i ? 0 : 1);
}
}
int res = 0x3f3f3f3f;
for (int i = 0; i < 4; ++i)
res = min(turn[ex][ey][i], res);
return res == 0x3f3f3f3f ? -1 : res;
}
int main()
{
cin >> n;
// getchar();
string s;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
{
cin >> s;
g[i][j] = s[0];
if (s == "A")
sx = i, sy = j;
if (s == "B")
ex = i, ey = j;
}
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 2; j <= n * 2 + 1; ++j)
// {
// char ch = getchar();
// if (ch == 'A')
// sx = i, sy = j / 2;
// if (ch == 'B')
// ex = i, ey = j / 2;
// if (j % 2 == 0)
// g[i][j / 2] = ch;
// }
// getchar();
// }
// for (int i = 1; i <= n; ++i)
// printf("%s\n", g[i] + 1);
// cout << sx << " " << sy << endl;
// cout << ex << " " << ey << endl;
cout << bfs();
return 0;
}
by qinshi0308 @ 2023-07-26 20:04:26
因为 getchar()
会读到空格、换行符
by qinshi0308 @ 2023-07-26 20:04:48
而 cin
不会
by qinshi0308 @ 2023-07-26 20:04:59
@LemonLeo
by qinshi0308 @ 2023-07-26 20:07:06
所以就有可能出现各种玄学错误