社区讨论
双端队列RE2个求助
P4554小明的游戏参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lw0oeq1f
- 此快照首次捕获于
- 2024/05/10 20:51 2 年前
- 此快照最后确认于
- 2024/05/10 22:42 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int n=1,m=1,x2,y2;
char mp[5050][5050];
int vis[5050][5050]={0};
struct AXI{
int x,y;
};
deque<AXI> de;
int dirx[]={1,0,-1,0};
int diry[]={0,1,0,-1};
int bfs(int x,int y){
de.push_back({x,y});
vis[x][y]=0;
while(!de.empty()){
auto t=de.front(); //取出队头元素
de.pop_front();
char c=mp[t.x][t.y];
for(int i=0;i<4;i++){
int tx=t.x+dirx[i];
int ty=t.y+diry[i];
if(tx<0||ty<0||tx>=n||ty>=m) continue;
if(vis[tx][ty]>=0) continue;
if(mp[tx][ty]==c){
vis[tx][ty]=vis[t.x][t.y];
de.push_front({tx,ty});
}
if(mp[tx][ty]!=c){
vis[tx][ty]=vis[t.x][t.y]+1;
de.push_back({tx,ty});
}
if(tx==x2&&ty==y2) return vis[tx][ty];
}
}
}
int main()
{ memset(vis,-1,sizeof(vis));
while(1){
cin>>n>>m;
if(n==0&&m==0) break;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mp[i][j];
}
}
int x1,y1;
cin>>x1>>y1>>x2>>y2;
int res=bfs(x1,y1);
cout<<res<<endl;
de.clear();
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...