社区讨论

双端队列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 条回复,欢迎继续交流。

正在加载回复...