对于朴素问题使用BFS和DFS的方法 yangzhihan

yangzhihan  •  28天前

相信大家都知道 在DFS与BFS中 最朴素的问题就要数老鼠走迷宫了 给定n行m列 用char读入 1表示可以走 0表示不能走 接下来 我——yangzhihan就给大家剖析一下代码 如有误请谅解 先是DFS(递归):

include<bits/stdc++.h>

using namespace std; const int MAX=105; int n,m,stx,sty,edx,edy,vis[MAX][MAX]; int dx[]={0,1,0,-1}; int dy[]={-1,0,1,0}; char maze[MAX][MAX]; bool flag=false; void dfs(int x,int y){

if(x==edx&&y==edy){
	flag=true;
	return;
}
for(int i=0;i<4;i++){
	int tx=x+dx[i];
	int ty=y+dy[i];
	if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&vis[tx][ty]==0&&maze[tx][ty]=='1'){
		vis[tx][ty]=1;
		dfs(tx,ty);
		vis[tx][ty]=0;
	}
}

} int main(){

cin>>n>>m;
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		cin>>maze[i][j];
cin>>stx>>sty>>edx>>edy;
vis[stx][sty]=1;
dfs(stx,sty);
if(flag==true)
	cout<<"YES";
else
	cout<<"NO";
return 0;

}

相信各位大佬都看得明白

接下来是BFS的朴素版本:

include<bits/stdc++.h>

using namespace std; const int MAX=105; int n,m,stx,sty,edx,edy,tail,head,vis[MAX][MAX],dis[MAX][MAX],qx[MAX],qy[MAX]; int dx[]={0,1,0,-1}; int dy[]={-1,0,1,0}; char maze[MAX][MAX]; void bfs(){

vis[stx][sty]=1;
head=tail=0;
qx[tail]=stx;
qy[tail]=sty;
tail++;
dis[stx][sty]=0;
while(head<tail){
	for(int i=0;i<4;i++){
		int tx=qx[head]+dx[i];
		int ty=qy[head]+dy[i];
		if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&vis[tx][ty]==0&&maze[tx][ty]=='1'){
			qx[tail]=tx;
			qy[tail]=ty;
			vis[tx][ty]=1;
			tail++;
			dis[tx][ty]=dis[qx[head]][qy[head]]+1;
		}
	}
	head++;
}

} int main(){

cin>>n>>m;
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		cin>>maze[i][j];
cin>>stx>>sty>>edx>>edy;
bfs();
cout<<dis[edx][edy];
return 0;

}

ok 接下来就是STL了 这个我建议用queue(队列)来存储 较为方便 废话不多说 献上代码:

include<bits/stdc++.h>

using namespace std; queue qx,qy; const int MAX=105; int n,m,stx,sty,edx,edy,tail,head,vis[MAX][MAX],dis[MAX][MAX]; int dx[]={0,1,0,-1}; int dy[]={-1,0,1,0}; char maze[MAX][MAX]; void bfs(){

qx.push(stx);
qy.push(sty);
dis[stx][sty]=0;
vis[stx][sty]=1;
while(!qx.empty()&&!qy.empty()){
	for(int i=0;i<4;i++){
		int tx=qx.front()+dx[i];
		int ty=qy.front()+dy[i];
		if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&vis[tx][ty]==0&&maze[tx][ty]=='1'){
			qx.push(tx);
			qy.push(ty);
			vis[tx][ty]=1;
			dis[tx][ty]=dis[qx.front()][qy.front()]+1;
		}
	} 
	qx.pop();
	qy.pop(); 
}

} int main(){

cin>>n>>m;
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		cin>>maze[i][j];
cin>>stx>>sty>>edx>>edy;
bfs();
cout<<dis[edx][edy];
return 0;

}

以上就是yangzhihan对走迷宫这一普通的题的看法啦! 有什么问题见评论区哟!! 谢谢

                            yangzhihan

暂未启用评论功能。