蒟蒻求问水题
查看原帖
蒟蒻求问水题
571348
PartiallyCorrect楼主2024/10/24 20:03
#include <bits/stdc++.h>
#define y1 yy
#define inf 0x3f3f3f3f
using namespace std;
const int N = 16385;
vector<char> g[N];
int n, m;
unordered_map<int, bool> used[N], vis[N];
int x, y, x1, y1;
int dx[8] = {-1, 0, 0, 1, -1, 1, -1, 1};
int dy[8] = {0, -1, 1, 0, 1, -1, -1, 1};
struct node
{
	int x, y, step;
};
inline bool check(int x, int y)
{
	return x >= 1 and x <= n and y >= 1 and y <= m and !used[x][y] and g[x][y] == 'O';
}
void bfs()
{
	queue<node> q;
	for(int i = 0 ; i < 8 ; i ++)
	{
		int tx = x1;
		int ty = y1;
		while(check(tx, ty))
		{
			vis[tx][ty] = true;
			tx += dx[i];
			ty += dy[i];
		}
	}
    used[x][y] = true;
	q.push({x, y, 0});
	while(!q.empty())
	{
		node t = q.front();
		q.pop();
		if(vis[t.x][t.y])
		{
			cout << t.step << endl;
			return ;
		}
		for(int i = 0 ; i < 4 ; i ++)
		{
			int tx = t.x + dx[i];
			int ty = t.y + dy[i];
			if(check(tx, ty))
			{
				used[tx][ty] = true;
				q.push({tx, ty, t.step + 1});
			}
		}
	}
}
signed main() 
{
	cin >> n >> m;
	for(int i = 0 ; i <= n ; i ++)
	{
		g[i].push_back('X');
		for(int j = 1 ; j <= m ; j ++)
		{
			if(i == 0)
			{
				g[i].push_back('X');
				continue;
			}
			char x;
			cin >> x;
			g[i].push_back(x);
		}
	}
	cin >> x >> y >> x1 >> y1;
	while(x and y and x1 and y1)
	{
        for(int i = 1 ; i <= n ; i ++)
		    used[i].clear(), vis[i].clear();
		bool f1 = true, f2 = true;
		for(int i = 0 ; i < 8 ; i ++)
			if(g[x + dx[i]][y + dy[i]] == 'O')
			{
				f1 = false;
				break;
			}
		for(int i = 0 ; i < 8 ; i ++)
			if(g[x1 + dx[i]][y1 + dy[i]] == 'O')
			{
				f2 = false;
				break;
			}
		if(f1 or f2)cout << "Poor Harry\n";
		else bfs();
        cin >> x >> y >> x1 >> y1;
	}
    return 0;
}
2024/10/24 20:03
加载中...