92分,一个RE,求帮忙找错
查看原帖
92分,一个RE,求帮忙找错
1087689
YOLO_IOLO楼主2024/7/27 20:39
//初始化能看到奖杯的点
//bfs直到遍历到标记的点
// 
#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[20100]; 
int n,m,nx,ny,finish_x,finish_y;
int v[20100];
int dx[5] = {0,0,1,0,-1};
int dy[5] = {0,1,0,-1,0};
int dx_[5] = {0,1,-1,-1,1};
int dy_[5] = {0,1,-1,1,-1};
struct node
{
	int x,y,data;
};
queue<node> que;
void init()//能看到奖杯的初始化 
{
	for (int i = 1;i <= 4;i++)//能看到奖杯的初始化 
		{
			int xx = finish_x,yy = finish_y;
			while(1)
			{
				//cout << 1;
				xx = xx + dx[i];
				yy = yy + dy[i];
				if (s[(xx - 1) * m + yy] != 'X' && xx >= 1 && xx <= n && yy >= 1 && yy <= m)
				{
					v[(xx - 1) * m + yy] = 2;
				}
				else
				{
					break;
				}
			}
		 }
		for (int i = 1;i <= 4;i++)//能看到奖杯的初始化 
		{
			int xx = finish_x,yy = finish_y;
			while(1)
			{
				//cout << 1;
				xx = xx + dx_[i];
				yy = yy + dy_[i];
				if (s[(xx - 1) * m + yy] != 'X' && xx >= 1 && xx <= n && yy >= 1 && yy <= m)
				{
					v[(xx - 1) * m + yy] = 2;
				}
				else
				{
					break;
				}
			}
		 }
}
void bfs()
{
	while(!que.empty())
	{
		//cout << 1; 
		int x = que.front().x;
		int y = que.front().y;
		int cnt = que.front().data;
		que.pop();
		for (int i = 1;i <= 4;i++)
		{
			//cout << 1; 
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (s[(xx - 1) * m + yy] != 'X' && v[(xx - 1) * m + yy] != 1 && xx >= 1 && xx <= n && yy >= 1 && yy <= m)
			{
				if (v[(xx - 1) * m + yy] == 2)
				{
					cout << cnt + 1 << endl;
					return;
				}
				v[(xx - 1) * m + yy] = 1;
				que.push(node{xx,yy,cnt + 1});
			}
		}
	}
	cout << "Poor Harry" << endl;
}
signed main()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
	{
		for (int j = 1;j <= m;j++)
		{
			cin >> s[(i - 1) * m + j];
		}
	}
	while(1)//多组数据 
	{
		cin >> finish_x >> finish_y >> nx >> ny;
		if (finish_x == 0 && finish_y == 0 && nx == 0 && ny == 0)//如果数据都是0则退出 
		{
			break;
		}
		//cout << 1; 
		while(!que.empty())//清空队列 
		{
			que.pop();
		}
		memset(v,0,sizeof(v));//清空之前走过的点
		if (nx == finish_x && ny == finish_y)//特判,如果 奖杯就在哈利脸上,直接输出 
		 {
		 	cout << 0 << endl;
		 	continue;
		 }
		 v[(finish_x - 1) * m + finish_y] = 2;
		init();//能看到奖杯的初始化 
		 if (v[(nx - 1) * m + ny] == 2)//特判,如果能看到奖杯的点就在哈利脸上,输出 
		 {
		 	cout << 0 << endl;
		 	continue;
		 }
		/*
		 for (int i = 1;i <= n;i++)
		 {
		 	for (int j = 1;j <= m;j++)
		 	{
		 		cout << s[(i - 1) * m + j] << ' ';
			 }
			 cout << endl;
		 }
		*/
		v[(nx - 1) * m + ny] = 1;//标记哈利最开始的点 
		que.push(node{nx,ny,0});//入队信息
		bfs();
	}
    return 0; 
}
/*
3 4
O X X O
X X O O
X O O O
3 2 2 4
3 3 1 1
0 0 0 0
*/
2024/7/27 20:39
加载中...