社区讨论

全RE求助

P2199最后的迷宫参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lz6tqn3v
此快照首次捕获于
2024/07/29 18:06
2 年前
此快照最后确认于
2024/07/29 19:43
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=1e3+5;
int n,m,vis[maxn][maxn];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int ddx[8]={0,0,1,1,1,-1,-1,-1};
int ddy[8]={1,-1,-1,0,1,-1,0,1};
vector<int>dis[int(1e5)];
string s[maxn];
struct node{
	int x,y;
};
queue<node>q;
void bfs(int x,int y){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			dis[i][j]=int(1e9);
	dis[x][y]=0;
	while(!q.empty()){
		node a=q.front();
		q.pop();
		for(int i=0;i<4;++i){
			int nx=dx[i]+a.x,ny=dy[i]+a.y;
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0&&s[nx][ny]!='X'){
				q.push({nx,ny});
				vis[nx][ny]=vis[a.x][a.y]+1;
			}
		}
	}
}
bool nice(int a,int b);
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cin>>s[i][j];
	while(1){
		int u,v,x,y;
		cin>>u>>v>>x>>y;
		if(u==0&&v==0&&x==0&&y==0)	break;
		int ans=dis[u-1][v-1];
		for(int i=0;i<8;++i){
			int a=u-1,b=v-1;
			while(nice(a+ddx[i],b+ddy[i])){
				a+=ddx[i];
				b+=ddy[i];
				ans=min(ans,dis[a][b]);
			}
			if(ans==int(1e9))	cout<<"Poor Harry";
			else	cout<<ans<<'\n';
		}
		vis[x][y]=1;
		q.push({x,y});
		bfs(x,y);
		vis[x][y]=0;
	}
	return 0;
}
bool nice(int a,int b){
	return a>0&&a<=n&&b>0&&b<=m&&s[a][b]!='X';
}

回复

0 条回复,欢迎继续交流。

正在加载回复...