Description
現在一只老鼠被困在了迷宮里！你需要判斷老鼠能否走出迷宮。

老鼠只能向上下左右四個方向移動。我們認為只要老鼠走到了迷宮的邊界即算走出迷宮。

Input
第一行輸入兩個整數 n, m (1?n,m?100) 表示迷宮地圖的尺寸。
接下來輸入 n 行，每行 m 個字符，表示迷宮地圖。其中 M 表示老鼠的位置，* 代表墻壁，. 代表空地。
Output
如果老鼠可以走出迷宮，則輸出一行 Yes，否則輸出一行 No。

Sample
Input

4 4 *.** *..* *.M* ****

Output

Yes

Hint

#include<bits/stdc++.h>using namespace std;const int N = 111;int n, m; int flag;//標記變量 char s[N][N];//迷宮 int book[N][N];//標記數組 int dx[] = {-1, 1, 0, 0};//定義兩個坐標數組，控制上下左右走 int dy[] = {0, 0, -1, 1};void DFS(int x, int y)//DFS跑迷宮 {book[x][y] = 1;if(x == 0 || y == 0 || x == n - 1 || y == m - 1)//到達邊界老鼠逃出來了{flag = 1;return ;}for(int i = 0; i < 4; i++)//遍歷四個方向，找出路{int xx = x + dx[i];int yy = y + dy[i];if(s[xx][yy] != '*' && !book[xx][yy] && xx >= 0 && xx < n && yy >= 0 && yy < m){DFS(xx, yy);}} } int main() {cin >> n >> m;int u, v;flag = 0;for(int i = 0; i < n; i++){cin >> s[i];for(int j = 0; j < m; j++){if(s[i][j] == 'M'){u = i;v = j;//記錄老鼠的位置}}}DFS(u, v);//可愛的老鼠就開始走迷宮了if(flag)cout << "Yes" << endl;elsecout << "No" << endl;return 0; }

總結

以上是生活随笔為你收集整理的K - 老鼠走迷宫(DFS)的全部內容，希望文章能夠幫你解決所遇到的問題。

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