蒟蒻求救(空间爆了)
查看原帖
蒟蒻求救(空间爆了)
354972
QiaoHongYi楼主2021/8/15 12:51
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
struct node
{
	int x, y, step;
};
int n, m_, x, y, xx, yy;
char m[17005][17005], win[17005][17005];
int see[8][2] = {{0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, 1}, {-1, -1}};
int move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void get_(int x, int y, int k)
{
	if (x <= 0 || y <= 0 || x > n || y > m_ || m[x][y] == 'X')
		return ;
	win[x][y] = 1;
	get_(x + see[k][0], y + see[k][1], k);
}
void init()
{
    for (int i = 1; i <= n; i++)
    	for (int j = 1; j <= m_; j++)
    		win[i][j] = 0;
}
int BFS(int sx, int sy)
{
	queue<node> q;
	node temp;
	temp.x = sx; temp.y = sy; temp.step = 0;
	q.push(temp);
	while (!q.empty())
	{
		for (int i = 0; i < 4; i++)
		{
			temp = q.front();
			temp.x += move[i][0];
			temp.y += move[i][1];
			temp.step += 1;
			if (m[temp.x][temp.y] == 'X') continue;
			if (temp.x > n || temp.x <= 0 || temp.y > m_ || temp.y <= 0) continue;
			if (win[temp.x][temp.y] == 1) return temp.step;
			q.push(temp);
		}
		q.pop();
	}
	return -1;
}
int main()
{
    cin >> n >> m_;
    for (int i = 1; i <= n; i++)
    	for (int j = 1; j <= m_; j++)
    		cin >> m[i][j];
    while (1)
    {
    	cin >> x >> y >> xx >> yy;
    	if (x == 0 && y == 0 && xx == 0 && yy == 0) break;
    	init();
    	for (int k = 0; k < 8; k++)
    		get_(x, y, k);
    	int answer = BFS(xx, yy);
    	if (answer != -1) cout << answer << endl;
    	else cout << "Poor Harry" << endl;
	}
	return 0;
}

2021/8/15 12:51
加载中...