用的二维广搜,88分,求优化
查看原帖
用的二维广搜,88分,求优化
1263285
Print_me楼主2024/7/22 17:35
#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x, y;
};

int n, m, sx, sy, fx, fy;;
char mp[1005][1005];
int dis[1005][1005];
bool vis[1005][1005];
bool flag[1005][1005];
int dx[]={1, 0, 0, -1, 1, 1, -1, -1};
int dy[]={0, 1, -1, 0, 1, -1, 1, -1};

void bfs(int x, int y)
{
	queue<node> q;
	memset(dis, -1, sizeof dis);
	memset(vis, false, sizeof vis);
	memset(flag, false, sizeof flag);
	for(int i=0; i<8; i++)
	{
		int nx=fx, ny=fy;
		while(1<=nx&&nx<=n&&1<=ny&&ny<=m&&mp[nx][ny]=='O')
		{
			flag[nx][ny]=true;
			nx+=dx[i];
			ny+=dy[i];
		}
	}
	q.push({x, y});
	vis[x][y]=true;
	dis[x][y]=0;
	while(q.size())
	{
		node now=q.front();
		q.pop();
		if(flag[now.x][now.y])
		{
			cout << dis[now.x][now.y] << endl;
			return ;
		}
		for(int i=0; i<4; i++)
		{
			int nx=now.x+dx[i], ny=now.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m)
			{
				continue;
			}
			if(mp[nx][ny]=='X')
			{
				continue;
			}
			if(vis[nx][ny])
			{
				continue;
			}
			dis[nx][ny]=dis[now.x][now.y]+1;
			vis[nx][ny]=true;
			q.push({nx, ny});
		}
	}
	cout << "Poor Harry\n";
	//return ;
}

int main()
{
	cin >> n >> m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			cin >> mp[i][j];
		}
	}
	while(true)
	{
		cin >> fx >> fy >> sx >> sy;
		if(sx==0&&sy==0)
		{
			break;
		}
		bfs(sx, sy);
	}
    return 0;
}
2024/7/22 17:35
加载中...