高橋先生住的小區是長方形的，被劃分成一個個格子。高橋先生想從家里去魚店，高橋先生每次可以走到他前后左右四個格子中的其中一個，但不能斜著走，也不能走出小區。
現在給出地圖：
s：代表高橋先生的家
g：代表魚店
.：代表道路
#：代表墻壁
高橋先生不能穿過墻壁。
輸入：第一行輸入n(1<=n<=500),m(1<=m<=500)代表小區的長和寬，接下來n行每行m個字符，描述小區中的每個格子。
輸出：如果高橋先生能到達魚店，輸出"Yes"，否則輸出"No"。
輸入輸出樣例 輸入 #1
復制
4 5
s####
…#

#…g 輸出 #1
復制
No輸入 #2
復制
4 4
…s
…
…
.g… 輸出 #2
復制
Yes輸入 #3
復制
10 10
s…
#########.
#…#.
#…####.#.
##…#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#…#… 輸出 #3
復制
No輸入 #4
復制
10 10
s…
#########.
#…#.
#…####.#.
##…#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#…#… 輸出 #4
復制
Yes輸入 #5
復制
1 10
s…####…g 輸出 #5
復制
No
思路：其實這道題目是簡單到不能簡單的一道深搜題目。但是我一開始的想法是需要回溯的，但是回溯做的話，是會超時的。如果當前狀態走過了，但是無法走到終點，按照之前的做法就取消標記，然后下次從別的點走到這個點的時候，結果仍然是走不到。那么我們就不取消標記了，如果某一個狀態可以直接走到終點，就直接返回，如果走不到終點，仍然不取消標記，別的點走到這一個點的時候，就會知道這個點無法走到終點。這一操作類似于記憶化的操作。
代碼如下：

#include <iostream> #include <string> using namespace std; int n,m; int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //定義方向數組 ； string maze[1100]; //定義地圖； bool vis[1100][1100]; //定義標記數組， 記錄當前點是否走過； bool in(int x,int y) {return x >= 0 && x < n && y >= 0 && y < m; } // 判斷函數，判斷當前點是否位于地圖內； bool dfs(int x,int y) {if (maze[x][y] == 'g') {return true;} //判斷是否到達；； vis[x][y] = 1; //標記當前點； 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; // 在(tx,ty)能到達，在(x,y)也能到達； }}}//若刪除標記，則從其他點也可搜索至(x,y)； //從(x,y)無法到達終點，則從其他點到達(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)) {cout << "Yes";} else {cout << "No";}return 0; }

ps：本題用bfs做更好。努力加油a啊

總結

以上是生活随笔為你收集整理的AT1350 深さ優先探索（洛谷 深度优先搜索+记忆化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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