題目：

從s到t,.意味著可以走，*意味著不能走，如果能走，輸出路徑，如果不能走，輸出no。
輸入：

5 6 ....S* .***.. .*..*. *.***. .T....

輸出：

....m* .***mm .*..*m *.***m .Tmmmm

分析與解答

1.整體思路：
我們先從第一個走的，因此先把第一個格子標(biāo)記為已走過，然后開始走第一個格子上下左右的相鄰格子，如果這個相鄰格子沒走過，而且從這個相鄰格子能走到下一個格子，那么就可以一直走下去，繼續(xù)調(diào)用dfs。

當(dāng)調(diào)用dfs直到無法走下一個格子，這時直接返回false，然后回到上一個格子，直到返回到最開始的那個格子，此時最開始的格子走另一個方向的格子。然后繼續(xù)重復(fù)之前的調(diào)用，直到找到終點。

2.推廣到dfs的研究方法：
1.處理搜索結(jié)束時的邊界條件

2.搜索：我們判斷是否能繼續(xù)往下搜，需要滿足下一個方向的坐標(biāo)在地圖里面，而且沒有被走過，而且沒遇到墻。如果滿足這些條件，就再調(diào)用dfs，繼續(xù)往下搜。

3.回溯：當(dāng)所有方向都搜完，也沒找到路徑，此時函數(shù)運行結(jié)束，這一層返回false，返回上一層的遞歸。返回之前，我們需要把訪問時做的標(biāo)記還原。返回上一層有可能就是改變方向繼續(xù)進(jìn)行新的搜索，直到達(dá)到邊界條件。

如果說最后到了邊界條件，那么底層的返回true，然后依次往上全部返回true，這樣dfs(x,y)就返回true。就說明從起始點xy走是可以到終點的。

如果說一直都沒有到邊界條件，那么也就是說我們一開始把起始點設(shè)定為已經(jīng)走過的點，然后上下左右搜索最后全部都回來了，此時第一層中那幾個if都用完了，于是就繼續(xù)往下走，也就是說，把起始的那個格子給初始化，并且返回false。

3.代碼的簡潔性：

然后由四個方向搜索，我們可以發(fā)現(xiàn)它有四個一摸一樣的if，只不過每次的x和y的值有所不同，那么我們就可以引入一個方向變量，int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; 這樣的話，我們就可以通過for循環(huán)和方向變量實現(xiàn)每次對xy的值的修改，然后再把if寫道for里面，這樣就不用把四個方向分開寫了，簡化了代碼量。

代碼

#include <iostream> #include <string> using namespace std; int n, m; string maze[110]; bool vis[110][110]; bool in(int x,int y){//防止走到地圖外面return 0<=x&&x<n&&0<=y&&y<m; } bool dfs(int x,int y){//x代表行，y代表列if(maze[x][y]=='T'){return true;}vis[x][y]=1;//標(biāo)記當(dāng)前點已走過maze[x][y]='m';//走過的點用字符m標(biāo)記int tx = x-1,ty=y;//向上搜if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){if(dfs(tx,ty)){return true;}}tx=x,ty=y-1;//左if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){if(dfs(tx,ty)){return true;}}tx=x+1,ty=y;//下if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){if(dfs(tx,ty)){return true;}}tx=x,ty=y+1;//右if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){if(dfs(tx,ty)){return true;}}vis[x][y]=0;maze[x][y]='.';return false; } int main() {// 輸入迷宮地圖cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];}int x,y;//確定起始位置for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(maze[i][j]=='S'){x=i,y=j;}}}if(dfs(x,y)){for(int i=0;i<n;++i){cout<<maze[i]<<endl;}}else{cout<<"NO!"<<endl;}return 0; }

用二維數(shù)組將上下左右搜索整合到一個for循環(huán)里。

#include <iostream> #include <string> using namespace std; int n, m; string maze[110]; bool vis[110][110]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; bool in(int x, int y) {return 0 <= x && x < n && 0 <= y && y < m; } bool dfs(int x, int y) {if(maze[x][y] == 'T'){return true;}vis[x][y]=1;maze[x][y]='m';for(int i=0;i<4;++i){int tx=x+dir[i][0];int ty=y+dir[i][1];if(in(tx,ty)&&maze[tx][ty]!='*'&&!vis[tx][ty]){if(dfs(tx,ty)){return true;}}}vis[x][y]=0;maze[x][y]='.';return false; } int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> maze[i];}int x, y;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == 'S') {x = i, y = j;}}}if (dfs(x, y)) {for (int i = 0; i < n; i++) {cout << maze[i] << endl;}} else {cout << "NO!" << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的(DFS)迷宫问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。