BFS TLE...
查看原帖
BFS TLE...
881317
spessert楼主2024/5/9 22:24
#include <bits/stdc++.h>   
using namespace std;  
int n,m;
char mp[2100][2100]; //地图
bool vis[2100][2100];
int dirx[]={1,0,-1,0}; //4个方向
int diry[]={0,-1,0,1};
struct AXI{
	int x,y;
};
queue<AXI> qu;

int bfs(int x,int y){
	
	vis[x][y]=true; 
	qu.push({x,y});
	int dep=1;
	while(!qu.empty()){
		int len=qu.size();
		while(len--){
			for(int i=0;i<4;i++){
				int tx=qu.front().x+dirx[i]; 
				int ty=qu.front().y+diry[i]; 
				if(tx<1||ty<1||tx>n||ty>m||vis[tx][ty]||mp[tx][ty]=='#'){
			      continue;
				}
				if(mp[tx][ty]=='d'){ //找到了 
					return dep;
				}
				qu.push({tx,ty});
				vis[tx][ty]=true;
			}
			qu.pop();
		}
		dep++;
	}
}
int main()  
{  
   //输入 
   cin>>n>>m;
   int x,y;//起点 
   for(int i=1;i<=n;i++){
   	for(int j=1;j<=m;j++){
   		cin>>mp[i][j];
   		if(mp[i][j]=='m'){
   			x=i,y=j;
   		}
   	}
   }
   //BFS 
   int res=bfs(x,y);
   //输出 
   if(res==0){
   	cout<<"No Way!";
   }else{
   	 cout<<res;
   }
  
   return 0;  
}
2024/5/9 22:24
加载中...