社区讨论
28求调BFS
P2199最后的迷宫参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m57y2p6x
- 此快照首次捕获于
- 2024/12/28 16:53 去年
- 此快照最后确认于
- 2025/11/04 12:15 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2E4 + 10;
char str[N];
int dist[N], n, m, sx, sy, wx, wy;
bool flag[N];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int px[] = {0, 1, 0, -1}, py[] = {1, 0, -1, 0};
void getLook()
{
memset(flag, 0, sizeof flag);
for(int i = 0; i < 8; ++ i)
{
int x = sx, y = sy;
while(1)
{
if(x < 0 || x >= n || y < 0 || y >= m || str[x * m + y] == 'X')
break;
flag[x * m + y] = true;
x += dx[i], y += dy[i];
}
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
queue <int> q;
q.push(wx * m + wy);
dist[wx * m + wy] = 0;
while(q.size())
{
int val = q.front();
q.pop();
if(flag[val])
return dist[val];
int x = val / m, y = val % m;
for(int i = 0; i < 4; ++ i)
{
int x1 = x + px[i], y1 = y + py[i];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m || str[x1 * m + y1] == 'X' || dist[x1 * m + y1] != 0x3f3f3f3f)
continue;
dist[x1 * m + y1] = dist[val] + 1;
q.push(x1 * m + y1);
}
}
return -1;
}
signed main()
{
cin >> n >> m;
for(int i = 0; i < n; ++ i)
{
string ss;
cin >> ss;
for(int j = 0; j < m; ++ j)
{
str[i * m + j] = ss[j];
}
}
while(1)
{
cin >> sx >> sy >> wx >> wy;
if(sx == 0 && sy == 0 && wx == 0 && wy == 0)
{
break;
}
sx --, sy --, wx --, wy --;
getLook();
int res = bfs();
if(res == -1)
cout << "Poor Harry" << "\n";
else
cout << res << "\n";
}
return 0;
}
必关
~~ 不关倒立~~
回复
共 1 条回复,欢迎继续交流。
正在加载回复...