没输出
查看原帖
没输出
377434
tian_jun_cheng楼主2022/1/31 15:58
#include<bits/stdc++.h>
using namespace std;
int ne[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int nne[8][2]={{-1,0},{-1,1},{-1,-1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int mp[5001][5001];
bool vis[5001][5001];
int n,m;
struct node{
	int x,y,t;
};
queue <node> q;
bool pd(int x,int y,int ex,int ey)
{
	if(x==ex && y==ey)
	    return true;
	for(int i=0;i<8;i++)
	{
		int nx=x+nne[i][0];
		int ny=y+nne[i][1];
		while(nx>=1 && nx<=n && ny>=1 && ny<=m && !mp[nx][ny])
		{
			if(nx==ex && ny==ey)
			    return true;
			nx=x+nne[i][0];
		    ny=y+nne[i][1];
		}
	}
	return false;
}
void bfs(int sx,int sy,int ex,int ey)
{
	node h,t;
	t={sx,sy,0};
	q.push(t);
	vis[sx][sy]=true;
	while(!q.empty())
	{
		h=q.front();
		q.pop();
		if(pd(h.x,h.y,ex,ey))
		{
			cout<<h.t;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int nx=h.x+ne[i][0];
			int ny=h.y+ne[i][1];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && !vis[nx][ny] && !mp[nx][ny])
			{
				t={nx,ny,h.t+1};
				q.push(t);
				vis[nx][ny]=true;
			}
		}
	}
	cout<<"Poor Harry";
	return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
		{
			char c;
    	    cin>>c;
         	if(c=='X')
    	        mp[i][j]=1;
    	    else
    	        mp[i][j]=0;
		} 
	int sx,sy,ex,ey;
	cin>>ex>>ey>>sx>>sy;
	while(sx!=0 || sy!=0 || ex!=0 || ey!=0)
	{
		memset(vis,false,sizeof(vis));
		bfs(sx,sy,ex,ey);
		cout<<endl;
		cin>>ex>>ey>>sx>>sy;
	}
	return 0;
}

2022/1/31 15:58
加载中...