數據

10 10 //格子行 列 #S######.# ......#..#.#.##.##.# .#........ ##.##.####....#....# .#######.#....#......####.###.....#...G#0 1 //起點9 8 //終點

輸出

22

dfs代碼：

#include <stdio.h>#define maxn 10001#define INF 100001int n,m;char maze[maxn][maxn];int d[maxn][maxn];int sx,sy,gx,gy;int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};int dfs(int x,int y){if(x==gx&&y==gy)return d[x][y]; //遞歸邊界 走到終點 for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==INF&&maze[nx][ny]!='#'&&d[gx][gy]==INF) //也要加個終點沒有被訪問到過，{ //不然，當走到終點，依舊會遞歸，直到全部格子走過一遍 d[nx][ny]=d[x][y]+1; printf("當前位置：%d %d 移動步數%d \n",nx,ny,d[nx][ny]);dfs(nx,ny);}}}int main(){scanf("%d %d",&n,&m);for(int i=0;i<n;i++)scanf("%s",&maze[i]);scanf("%d %d %d %d",&sx,&sy,&gx,&gy);for(int i=0;i<n;i++)for(int j=0;j<m;j++)d[i][j]=INF;d[sx][sy]=0;dfs(sx,sy);printf("%d",d[gx][gy]);return 0;}

bfs代碼：

#include <stdio.h> #include <utility> #include <queue> #define maxn 10001 #define INF 1000000 using namespace std; typedef pair<int, int>P; char maze[maxn][maxn]; int sx,sy; int gx,gy; int n,m; int d[maxn][maxn]; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; int bfs() {queue<P>s;for(int i=0;i<n;i++)for(int j=0;j<m;j++)d[i][j]=INF;s.push(P(sx,sy));d[sx][sy]=0;while(s.size()){P p=s.front();s.pop();if(p.first==gx&&p.second==gy)break;for(int i=0;i<4;i++){int nx=p.first+dx[i];int ny=p.second+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==INF&&maze[nx][ny]!='#'){s.push(P(nx,ny));d[nx][ny]=d[p.first][p.second]+1;}}}return d[gx][gy]; } int main() {int i,j;scanf("%d %d",&n,&m);for(i=0;i<n;i++)scanf("%s",&maze[i]);scanf("%d %d %d %d",&sx,&sy,&gx,&gy);printf("%d",bfs());return 0; }

總結

以上是生活随笔為你收集整理的dfs和bfs走迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。