社区讨论
全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 条回复,欢迎继续交流。
正在加载回复...