求救,空间炸完
查看原帖
求救,空间炸完
667558
_Kamisato_Ayaka_楼主2022/5/3 16:04
#include<bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,-1,1,-1};
const int dy[]={0,1,0,-1,1,1,-1,-1};
char mp[16400/2][16400/2];
int vis[16400/2][16400/2],n,m,sx,sy,fx,fy;
bool flag;
bool check(int x,int y)
{
	for(int i=0;i<8;i++){
		int nx=x;
		int ny=y;
		if(nx==fx && ny==fy) return true;
		while(nx<=n && nx>=1 && ny<=m && ny>=1){
			nx+=dx[i];
			ny+=dy[i];
			if(mp[nx][ny]=='X')break;
			if(nx==fx && ny==fy) return true;
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	flag=false;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	do{
		queue<int>qx;
		queue<int>qy;
		queue<int>step;
		cin>>fx>>fy>>sx>>sy;
		if(fx==0 && fy==0 && sx==0 && sy==0) break;
		memset(vis,0,sizeof(vis));
		if(check(sx,sy)){
			cout<<0<<endl;
			continue;
		}
		qx.push(sx);
		qy.push(sy);
		step.push(0);
		vis[sx][sy]=1;
		flag=false;
		while(!qx.empty()){
			int px=qx.front();
			int py=qy.front();
			int st=step.front();
			for(int i=0;i<4;i++){
				int rx=px+dx[i];
				int ry=py+dy[i];
				if(rx<1||rx>n||ry<1||ry>m) continue;
				if(vis[rx][ry]) continue;
				if(mp[rx][ry]=='X') continue;
				vis[rx][ry]=1;
				qx.push(rx);
				qy.push(ry);
				step.push(st+1);
				if(check(rx,ry)==true){
					cout<<st+1<<endl;
					flag=true;
					break;
				}
			}
			if(flag){
				break;
			}
			qx.pop();
			qy.pop();
			step.pop();
		}
		if(!flag){
			cout<<"Poor Harry"<<endl;
		}
	}while(fx!=0 || fy!=0 || sx!=0 || sy!=0);
	return 0;
}

队列写的

2022/5/3 16:04
加载中...