WA+MLE求助,使用的二维广搜
查看原帖
WA+MLE求助,使用的二维广搜
1168930
a3395356240楼主2024/7/16 11:20
#include<bits/stdc++.h>
using namespace std;
int n,m,x,x2,y,y2;

vector<vector<int> >a;
vector<vector< int > > flag;
int dx[]={1,1,1,-1,-1,-1,0,0};
int dy[]={1,0,-1,0,-1,1,1,-1};


struct node{
	int x;
	int y;
	int step;
};

void chuli(int x3,int y3,int i){
	while(x3>=1&&y3>=1&&x3<=n&&y3<=m&&a[x3][y3]!=0){
		flag[x3][y3]=-1;
		x3+=dx[i];
		y3+=dy[i];
	}
}


int bfs(){
	queue < node > q;
	node p;
	p.x=x2,p.y=y2,p.step=0;
	q.push(p);
	
	for(int i=0;i<8;i++)
		chuli(x,y,i);//进行预处理,把能看到的地方标记
		
		
	if(flag[x2][y2]==-1){
		return 0;
	}
	
	while(!q.empty()){
		p=q.front();
		q.pop();
		flag[p.x][p.y]=1;
		for(int i=0;i<8;i++)
		{
			int nx=p.x+dx[i];
			int ny=p.y+dy[i];
			if(a[nx][ny]!=0&&nx>=1&&nx<=n&&ny>=1&&ny<=m&&flag[nx][ny]!=1)
			{
				if(flag[nx][ny]==-1)
					return p.step+1;
					
				node n;
				n.x=nx;
				n.y=ny;
				n.step=1+p.step;
				q.push(n);
			}
		}
	}
	return -1;
}
int main()
{
	cin>>n>>m;
	a.resize((n+5),vector<int>(m+5));
	
	flag.resize((n+5),vector<int>(m+5));
	//标记数组,记录搜过的点
	for(int i=1;i<=n;i++)
	{
		 for(int j=1;j<=m;j++)
		 {
			char k;
			cin>>k;
			if(k=='O') a[i][j]=1;
			else a[i][j]=0;
		}
	}
	
	cin>>x>>y>>x2>>y2;
	while(x!=0&&y!=0&&x2!=0&&y2!=0){
		int f0=bfs();
		
		if(f0!=-1){
			cout<<f0<<endl;
		}else cout<<"Poor Harry"<<endl;
		
		cin>>x>>y>>x2>>y2;
	}	 
}
2024/7/16 11:20
加载中...