有关dfs、bfs解决迷宫问题的个人见解

可以使用BFS或者DFS方法解决的迷宫问题！

题目如下：

kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？

输入描述:

第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30)

后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置，'.'代表道路，'*'代表墙壁，'e'代表出口。保证输入合法。

输出描述:

若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫）

若没有出口可以抵达，则输出-1。

示例1

输入

复制

6 8
e.*.*e.*
.**.*.*e
..*k**..
***.*.e*
.**.*.**
*......e

输出

复制

2 7

说明

可供选择坐标为[4,7]和[6,8]，到kotori的距离分别是8和7步。


DFS解决如下：

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 char map[100][100];
 5 int use[100][100];
 6 int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; //上下左右四个方向
 7 int minn = 999999999;
 8 
 9 int pan(int x,int y)
10 {
11     if(0 <= x && x <= 5 && 0 <= y && y <= 7 && (map[x][y] == '.' || map[x][y]=='k')) return 1;
12     else return 0;
13 }
14 
15 void dfs(int x,int y,int step)
16 {
17     // 递归程序，必须要设置整个程序的出口，在dfs中，即当走到迷宫出口处即可结束程序
18     if(map[x][y] == 'e')
19     {
20         cout<<"success"<<endl;
21         if(step < minn) minn = step;
22         return;
23     }
24     for(int i = 0; i < 4; i++)
25     {
26         if(pan(x,y) && use[x][y] != 1) 
27         {
28             use[x][y] = 1;
29             cout<<"dd";
30             cout<<"  "<<map[x+dir[i][0]][y+dir[i][1]]<<endl;
31             dfs(x+dir[i][0],y+dir[i][1],step+1);
32             use[x][y] = 0;
33         }        
34     }
35 
36 }
37 int main()
38 {
39     int n;
40     int m;
41     cin >> n >> m;
42     // 4,5行已经定义了map和use数据，所以在此处不必int map[n][m],直接map[n][m]即可，否则报错 
43     map[n][m];
44     use[n][m];
45     memset(use,0,sizeof(use));
46     int x_start = 0;
47     int y_start = 0;
48     int step = 0;
49     for(int i = 0; i < n; i++)
50     {
51         for(int j = 0; j < m; j++)
52         {
53             cin >> map[i][j];
54             if(map[i][j] == 'k')
55             {
56                 x_start = i;
57                 y_start = j;
58             }
59         }
60     }
61     cout<<x_start<<" "<<y_start<<endl;
62     dfs(x_start, y_start, step);
63     cout<<"最小步数"<<minn<<endl;
64 }

BFS解决如下：

（1）自己写的有缺陷的代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<string.h>
 4 using namespace std;
 5 char map[100][100];
 6 int vis[100][100];
 7 int use[100][100];
 8 int m,n;
 9 int x_start,y_start;
10 queue<int> que;
11 int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
12 int cnt = 0;
13 int mi = 999999;
14 
15 int pan(int x,int y)
16 {
17     if(0 <= x && x <= n-1 && 0 <= y && y <= m -1 &&map[x][y] != '*') return 1;
18     else return 0;
19 }
20 
21 void bfs(int x,int y)
22 {
23     int x1 = x;
24     int y1 = y;
25     while(!que.empty())
26     {
27         vis[x1][y1] = 1;
28         x1 = que.front();
29         que.pop();
30         y1 = que.front();
31         que.pop(); 
32         cout<<"x1:"<<x1<<" "<<"y1:"<<y1<<endl; 
33         if(map[x1][y1] == 'e')
34         {
35             if(use[x1][y1] == 0)
36             {
37                 cnt++;
38                 use[x1][y1]=1;
39             }
40             continue;
41         }
42 
43         for(int i = 0; i < 4; i++)
44         {
45             int xx = x1 + dir[i][0];
46             int yy = y1 + dir[i][1];
47             if(pan(xx,yy) && vis[xx][yy] == 0)
48             {
49                 cout<<"dd"<<endl;
50                 cout<<xx<<" "<<yy<<endl;
51                 que.push(xx);
52                 que.push(yy);
53                 vis[xx][yy] = 1;
54             }
55         }    
56     }    
57 }
58 
59 int main()
60 {
61     memset(vis,0,sizeof(vis));
62     memset(use,0,sizeof(use));
63     cin >> n >> m;
64     for(int i = 0; i < n; i++)
65     {
66         for(int j = 0; j < m; j++)
67         {
68             cin >> map[i][j];
69             if(map[i][j] == 'k')
70             {
71                 x_start = i;
72                 y_start = j;
73             }
74         }
75     }
76     que.push(x_start);
77     que.push(y_start);
78     bfs(x_start,y_start);
79     cout<<cnt<<endl;
80 
81 }

对于每个点每个状态我采用的是直接利用队列记录他们的坐标值，而不是如AC代码一样利用结构体记录每个点的每个状态。所以导致我整个程序还是存在很大的缺陷，例如求最短路径的时候就比较困难。

所以对于BFS的题目，强烈建议把每个点每个状态先用结构体表示，然后利用队列记录这些结构体即可。

（2）AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[35][35];
 4 bool usd[35][35];
 5 int Move[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
 6 struct now
 7 {
 8     int x,y,dis;
 9 };
10 queue<now>q;
11 int main()
12 {
13     int n,m,cnt=0;
14     scanf("%d%d",&n,&m);
15     now s;
16     for(int i=1;i<=n;++i)
17         for(int j=1;j<=m;++j)
18         {
19             cin>>a[i][j];
20             if(a[i][j]=='k')
21             {
22                 s.x=i;
23                 s.y=j;
24                 s.dis=0;
25             }
26         }
27     q.push(s);
28     int ans=99999999;
29     while(!q.empty())
30     {
31         now Now=q.front();
32         q.pop();
33         if(a[Now.x][Now.y]=='e')
34         {
35             if(!usd[Now.x][Now.y])
36             {
37                 ++cnt;
38                 ans=min(ans,Now.dis);
39             }
40             usd[Now.x][Now.y]=true;
41             continue; //到达出口"e"处就必须跳过一下步骤，不能在对出口点“e”进行下面的扩展步骤(上下左右)
42         }
43         usd[Now.x][Now.y]=true;
44         for(int i=0;i<4;++i)
45         {
46             int xx=Now.x+Move[i][0],yy=Now.y+Move[i][1],d=Now.dis;
47             if(xx<=n&&xx>=1&&yy>=1&&yy<=m&&!usd[xx][yy]&&a[xx][yy]!='*')
48             {
49                 now t;
50                 t.x=xx;
51                 t.y=yy;
52                 t.dis=d+1;
53                 q.push(t);
54             }
55         }
56     }
57     if(!cnt)
58         return !printf("-1
");
59     printf("%d %d
",cnt,ans);
60     return 0;
61 }

带路径输出的BFS(路径的输出主要依靠递归程序，记录每个点的结构体还需要记录每个点的前驱节点的坐标)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[35][35];
 4 bool usd[35][35];
 5 int Move[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
 6 struct now
 7 {
 8     int x,y,dis,pre_x,pre_y;
 9 };
10 queue<now>q;
11 now buf[35];
12 int count1 = 0;
13 
14 void print(int x,int y)
15 {
16     int temp;
17     for(int i = 0; i < count1; i++)
18     {
19         if(buf[i].x == x && buf[i].y == y) temp = i;
20     }
21     if(x == -1 && y == -1) return;
22     else
23     {
24         print(buf[temp].pre_x,buf[temp].pre_y);
25         cout<<"("<<x<<","<<y<<")"<<endl;
26     }
27 }
28 
29 int main()
30 {
31     int n,m,cnt=0;
32     scanf("%d%d",&n,&m);
33     now s;
34     for(int i=1;i<=n;++i)
35         for(int j=1;j<=m;++j)
36         {
37             cin>>a[i][j];
38             if(a[i][j]=='k')
39             {
40                 s.x=i;
41                 s.y=j;
42                 s.pre_x = -1;
43                 s.pre_y = -1;
44                 s.dis=0;
45             }
46         }
47     q.push(s);
48     int ans=99999999;
49     while(!q.empty())
50     {
51         now Now=q.front();
52         buf[count1++] = Now;
53         q.pop();
54         if(a[Now.x][Now.y]=='e')
55         {
56             if(!usd[Now.x][Now.y])
57             {
58                 ++cnt;
59                 ans=min(ans,Now.dis);
60                 usd[Now.x][Now.y]=true;
61                 print(Now.x,Now.y);
62             }
63             continue;
64         }
65         usd[Now.x][Now.y]=true;
66         for(int i=0;i<4;++i)
67         {
68             int xx=Now.x+Move[i][0],yy=Now.y+Move[i][1],d=Now.dis;
69             if(xx<=n&&xx>=1&&yy>=1&&yy<=m&&!usd[xx][yy]&&a[xx][yy]!='*')
70             {
71                 now t;
72                 t.x=xx;
73                 t.y=yy;
74                 t.pre_x = Now.x;
75                 t.pre_y = Now.y;
76                 t.dis=d+1;
77                 q.push(t);
78             }
79         }
80     }
81     if(!cnt)
82         return !printf("-1
");
83     printf("%d %d
",cnt,ans);
84 //    for(int i = 0; i < count1; i++)
85 //    {
86 //        cout<<buf[i].x<<" "<<buf[i].y<<" "<<buf[i].pre_x<<" "<<buf[i].pre_y<<endl;
87 //    }
88     return 0;
89 }

利用dfs解决最大连通块问题！

题目描述

农场主约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度害怕水的消息而恶化。

然而，他的保险公司只会根据他农场最大的“湖”的大小来偿还他一笔钱。

农场表示为一个矩形网格，有N（1≤N≤100）行和M（1≤M≤100）列。网格中的每个格子要么是干的，

要么是被淹没的，而恰好有K（1≤K≤N×M）个格子是被淹没的。正如人们所期望的，一个“湖”有一个

中心格子，其他格子通过共享一条边（只有四个方向，对角线不算的意思）与之相连。任何与中央格子共享一条边或与中央格

子相连的格子共享一条边的格子都将成为湖的一部分。

输入描述:

第一行有三个整数N,M,K，分别表示这个矩形网格有N行，M列，K个被淹没的格子。

接下来K行，每一行有两个整数R,C。表示被淹没的格子在第R行，第C列。

输出描述:

输出最大的“湖”所包含的格子数目

输入

输出

 1 #include<iostream>
 2 using namespace std;
 3 int map[100][100];
 4 int vis[100][100] = {0};
 5 int used[100][100] = {0};
 6 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
 7 int n,m,k;
 8 int cnt = 1;
 9 int maxx = -1;
10 int pan(int x,int y)
11 {
12     if(map[x][y] == 1 && 0 <= x && x <= n-1 && y <= m-1 && y >= 0 && vis[x][y] == 0 && used[x][y]==0)
13     {
14         return 1;
15     }
16     else return 0;
17 }
18 
19 void dfs(int x,int y,int c) //连通块问题就不像迷宫问题有递归出口！！！！
20 {
21     vis[x][y] = 1;
22 //    cout<<x<<" "<<y<<" dd"<<endl; 
23     for(int i = 0; i < 4; i++)
24     {
25         int xx = x + dir[i][0];
26         int yy = y + dir[i][1];
27         if(pan(xx,yy))
28         {
29 //            cout<<xx<<" "<<yy<<endl;
30             vis[xx][yy] = 1;
31             used[xx][yy] = 1;      // used数组是防止多次记录连通块！
32             cnt++;
33             c = cnt;   // 这一块必须注意，不能直接传入cnt，因为递归函数是放在栈中，倘若传入cnt，递归函数出栈时，cnt的值也会变化，所以用c代替cnt.
34             dfs(xx,yy,c);
35             vis[xx][yy] = 0;
36         }
37     }
38 }
39 
40 int main()
41 {
42     cin >> n >> m >> k;
43     map[n][m];
44     for(int i = 0; i < n; i++)
45     {
46         for(int j = 0; j < m; j++) map[i][j] = 0;
47     }
48     for(int i = 0; i < k; i++)
49     {
50         int x,y;
51         cin >> x >> y;
52         map[x-1][y-1] = 1;
53     }
54 //    for(int i = 0; i < n; i++)     打印整个地图 
55 //    {
56 //        for(int j = 0; j < m; j++)
57 //        {
58 //            cout<<map[i][j];
59 //        }
60 //        cout<<endl;
61 //    }
62     for(int i = 0; i < n; i++)
63     {
64         for(int j = 0; j < m; j++)
65         {
66             cnt = 1;
67             if(map[i][j] == 1)
68             {
69                 dfs(i,j,cnt);
70                 if(cnt > maxx) maxx = cnt;
71             }
72         }
73     }
74     cout<<maxx<<endl;
75 
76 }

本题总结：

1.利用dfs解决连通块问题与利用dfs解决迷宫问题存在一定的区别：

（1）迷宫问题有固定的入口或者出口，而连通块问题就没有所谓的出口或者入口，它需要遍历map[][]数组中的每个元素！