社区讨论

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 条回复,欢迎继续交流。

正在加载回复...