DFS与DFS迷宫问题

一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数n 和 m，表示这是一个 n×m 的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出一个字符串，如果蒜头君可以逃出迷宫输出"yes"，否则输出"no"。

数据范围

1≤n,m≤10。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

3 4
S**.
..*.
***T

样例输出

no

样例输入

3 4
S**.
....
***T

样例输出

yes

 1 #include<iostream>
 2 using namespace std;
 3 int n,m,beginx,beginy;
 4 bool mark[11][11]={false};
 5 char map[11][11];
 6 int x[4]={0,-1,1,0},y[4]={-1,0,0,1};
 7 bool flag=false;
 8 bool check(int r,int c){
 9     if (r>=0&&r<n&&c>=0&&c<m)
10         return true;
11     return false;    
12 }
13 void DFS(int r,int c){
14 
15     int newx,newy;
16     for (int  i = 0; i < 4; i++)
17     {
18         newx = r +x[i];
19         newy = c + y[i];
20         if (check(newx,newy)&&!mark[newx][newy])
21         {
22             mark[newx][newy]=true;
23             if (map[newx][newy]=='T')
24             {
25                 flag=true;
26                 cout<<"yes"<<endl;
27                 return;
28             }
29             if (map[newx][newy]=='.')
30             {
31                 mark[newx][newy]=true;
32                 DFS(newx,newy);
33                 // cout<<"newx = "<<newx<<"  newy ="<<newy<<endl; 
34             }
35         }
36     }
37 }
38 int main(){
39     cin>>n>>m;
40     for (int i = 0; i < n; i++)
41     {
42         cin>>map[i];
43         for (int j = 0; j < m; j++)
44         {
45             if (map[i][j]=='S')
46             {
47                 beginx= i;
48                 beginy=j;
49             }
50         }
51     }
52     mark[beginx][beginy];
53     DFS(beginx,beginy);
54     if (!flag)
55     {
56         cout<<"no"<<endl;
57     }
58     
59 }

 

因上求缘，果上努力~~~~ 作者：每天卷学习，转载请注明原文链接：https://www.cnblogs.com/BlairGrowing/p/12723687.html