蒟蒻BFS WA on #12求助
查看原帖
蒟蒻BFS WA on #12求助
781690
Wanghaochen28楼主2025/1/16 14:56
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};
struct node
{
	int x, y;
};
queue<node> q;
int n, m, dis[1005][1005], sx, sy, fx, fy;
char g[1005][1005];
bool in(int x, int y)
{
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
bool see(int x, int y)
{
	if (x == fx && y == fy)
	{
		return true;
	}
	for (int i = 0; i < 8; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		while (in(nx, ny) && g[nx][ny] == 'O')
		{
			if (nx == fx && ny == fy)
			{
				return true;
			}
			nx += dx[i];
			ny += dy[i];
		}
	}
	return false;
}
int bfs()
{
	q = queue<node>();
	memset(dis, -1, sizeof(dis));
	q.push({sx, sy});
	dis[sx][sy] = 0;
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (see(x, y))
		{
			return dis[x][y];
		}
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (in(nx, ny) && dis[nx][ny] == -1 && g[nx][ny] == 'O')
			{
				q.push({nx, ny});
				dis[nx][ny] = dis[x][y] + 1;
			}
		}
	}
	return -1;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> g[i][j];
		}
	}
	while (true)
	{
		cin >> fx >> fy >> sx >> sy;
		if (fx == 0)
		{
			break;
		}
		int ans = bfs();
		if (ans == -1)
		{
			cout << "Poor Harry" << endl;
		}
		else
		{
			cout << ans << endl;
		}
	}
	return 0;
}
2025/1/16 14:56
加载中...