88 pts RE 求救,已开动态数组
查看原帖
88 pts RE 求救,已开动态数组
639085
SSqwq_楼主2023/10/19 21:21

#12 RE

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
	int x,y,step;
};
queue<Node> qu;
vector<int> vis[16385],a[16385],ac[16385];
int n,m,q;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
int sx,sy,tx,ty,flag,ans;
void bfs2(){
	for(int i=0;i<=n+100;++i){
		ac[i].clear();
		ac[i].push_back(0);
		for(int j=1;j<=m+100;++j){
			ac[i].push_back(0);
		}
	}
	ac[tx][ty]=1;
	for(int i=1;a[tx+i][ty]==0&&tx+i<=n;++i){
		ac[tx+i][ty]=1;
	}
	for(int i=1;a[tx-i][ty]==0&&tx-i>=1;++i){
		ac[tx-i][ty]=1;
	}
	for(int i=1;a[tx][ty+i]==0&&ty+i<=m;++i){
		ac[tx][ty+i]=1;
	}
	for(int i=1;a[tx][ty-i]==0&&ty-i>=1;++i){
		ac[tx][ty-i]=1;
	}
	for(int i=1;a[tx+i][ty+i]==0&&tx+i<=n&&ty+i<=m;++i){
		ac[tx+i][ty+i]=1;
	}
	for(int i=1;a[tx-i][ty+i]==0&&tx-i>=1&&ty+i<=m;++i){
		ac[tx-i][ty+i]=1;
	}
	for(int i=1;a[tx-i][ty-i]==0&&ty-i>=1&&tx-i>=1;++i){
		ac[tx-i][ty-i]=1;
	}
	for(int i=1;a[tx+i][ty-i]==0&&ty-i>=1&&tx+i<=n;++i){
		ac[tx+i][ty-i]=1;
	}
}
void bfs1(){
	flag=0;
	for(int i=0;i<=n+100;++i){
		vis[i].clear();
		vis[i].push_back(0);
		for(int j=1;j<=m+100;++j){
			vis[i].push_back(0);
		}
	}
	while(!qu.empty())qu.pop();
	Node p;
	p.x=sx;
	p.step=0;
	p.y=sy;
	vis[sx][sy]=1;
	qu.push(p);
	while(!qu.empty()){
		Node head=qu.front();
		qu.pop();
		int x=head.x;
		int y=head.y;
		int step=head.step;
		if(ac[x][y]){
			flag=1;
			ans=min(ans,step);
			return;
		}
		for(int i=0;i<4;++i){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny]||a[nx][ny]){
				continue;
			}
			Node p;
			p.x=nx;
			p.y=ny;
			p.step=step+1;
			vis[nx][ny]=1;
			qu.push(p);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<=n+100;++i){
		a[i].push_back(0);
		for(int j=1;j<=m+100;++j){
			a[i].push_back(0);
		}
	}
	for(int i=1;i<=n;++i){
		string x;
		cin>>x;
		x=' '+x;
		for(int j=1;j<=m;++j){
			if(x[j]=='X')a[i][j]=1;
		}
	}
	while(1){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if(a==b&&c==d&&a==c&&a==0){
			break;
		}
		tx=a,ty=b,sx=c,sy=d;
		bfs2();
		ans=2e9;
		bfs1();
		if(!flag){
			cout<<"Poor Harry\n";
		}
		else{
			cout<<ans<<"\n";
		}
	}
	return 0;
}
2023/10/19 21:21
加载中...