DFS&BFS总结
DFS&BFS总结
目录..........................................................................................1
B - LakeCounting.............................1
C - Red and Black............................8
D - 胜利大逃亡................................14
A - 迷宫问题.....................................................................20
小结..........................................................................................27
基础知识不再介绍，直接看题目吧(*^▽^*)。
POJ2386（https://vjudge.net/problem/POJ-2386）
题面：
Lake Counting
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 42011 |
|
Accepted: 20842 |
Description
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
Output
* Line 1: The number of ponds in Farmer John's field.
Sample Input
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
Sample Output
3
Hint
OUTPUT DETAILS:
There are three ponds: one in the upper left, one in the lower left,and one along the right side.
题目大意：
给你一个n*m的矩阵，每个点有两个状态，‘W’和‘.’。
如果一个W在以另一个W为中心的3*3矩阵中，则认为它们相邻。
* * *
*W*
* * *
在上图的八个位置的任一一个W都与中心的W相邻。
所有相邻的W构成一个连通块
目标是对于一个给定的矩阵，求连通块的数目，很好理解吧(#^.^#)
分析：
对于这类需要遍历所有状态的要求，一般使用DFS，毕竟递归函数更容易理解。所以我们可以遍历整个矩阵，每遇到一个‘W’就把它以及与它相邻的所有W改成‘.’，同时结果加1 。这样，每次我们遇到一个新的W，它一定不与之前找到的所有连通块相邻（如果相邻的话它就被改成‘.’了）。
代码：
首先遍历矩阵：
for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { judge(i, j);//对每一个块进行的操作 } }
对每一块进行的操作：
void judge(int i, int j)
{
if(s[i][j] == 'W')
{
dfs(i, j);
cnt++;
}
}dfs函数：
在本题中，需要遍历八个方块，可以用两个for循环枚举实现（当dx=dy=0时会遍历到自己，所以要在函数开始将s[x][y]改成‘.’）
void dfs(int x, int y)
{
s[x][y] = '.';
for(int dx = -1; dx <= 1; dx++)
{
for(int dy = -1; dy <= 1; dy++)
{
int x1 = x + dx;
int y1 = y + dy;
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
if(s[x1][y1] == 'W')dfs(x1, y1);
}
}
}AC代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e2 + 10;
char s[maxn][maxn];
int n, m;
int cnt = 0;
void dfs(int x, int y)
{
s[x][y] = '.';
for(int dx = -1; dx <= 1; dx++)
{
for(int dy = -1; dy <= 1; dy++)
{
int x1 = x + dx;
int y1 = y + dy;
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
if(s[x1][y1] == 'W')dfs(x1, y1);
}
}
}
void judge(int i, int j)
{
if(s[i][j] == 'W')
{
dfs(i, j);
cnt++;
}
}
void work()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%s", s[i]);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
judge(i, j);//对每一个块进行的操作
}
}
printf("%d\n", cnt);
}
int main()
{
work();
return 0;
}POJ1979(https://vjudge.net/problem/POJ-1979)
题面：
Red and Black
Time Limit: 1000MS |
|
Memory Limit: 30000K |
Total Submissions: 41475 |
|
Accepted: 22470 |
Description
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
'.' - a black tile
'#' - a red tile
'@' - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.
Output
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#aaa@qq.com#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
aaa@qq.com
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
大意：
给你一个n*m的矩阵，每个点三种状态，‘.’或‘#’或‘@’。
一个人从‘@’出发，每次可以走上下左右四个方向，‘#’是墙不能走，问能走到多少个‘.’。
思路：
没啥好说的..直接对@所在点dfs一下就好了(*￣︶￣)
dfs函数
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*这里只能走四个方向，直接把这四个方向的坐标变化记做常量数组就好*/
void dfs(int x, int y)
{
if(vis[x][y]) return;
vis[x][y] = true;
cnt++;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
if(s[x1][y1] == '.')dfs(x1, y1);
}
}
}AC代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2e1 + 10;
char s[maxn][maxn];
int n, m;
bool vis[maxn][maxn];
int cnt = 0;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
void dfs(int x, int y)
{
if(vis[x][y]) return;
vis[x][y] = true;
cnt++;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
if(s[x1][y1] == '.')dfs(x1, y1);
}
}
}
void work()
{
memset(s, 0, sizeof(s));
memset(vis, 0, sizeof(vis));
cnt = 0;
for(int i = 0; i < n; i++) scanf("%s", s[i]);
int x, y;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(s[i][j] == '@')
{
x = i;
y = j;
}
}
}
dfs(x, y);
printf("%d\n", cnt);
}
int main()
{
while(scanf("%d%d", &m, &n) == 2 && n + m)
{
work();
}
return 0;
}HDU1253（https://vjudge.net/problem/HDU-1253）
题面：
胜利大逃亡
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42185 Accepted Submission(s): 14670
Problem Description
Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.
魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.
Input
输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫)
特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.
Output
对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.
Sample Input
1
3 3 4 20
0 1 1 1
0 0 1 1
0 1 1 1
1 1 1 1
1 0 0 1
0 1 1 1
0 0 0 0
0 1 1 0
0 1 1 0
Sample Output
11
题意：
给了一个a*b*c的魔方，每次有八个方向移动，问能否在时间t内从右下角到左上角。
这也是搜索类的题目，但与之前不同的是。前两道题我们都需要遍历所有的状态（或者说“点”）才能得出正确答案。但像这种求最短路或者最少操作次数的题目，只需要找出最短路径就可以了（即不必要遍历所有状态也可以找到最短路径，这里就不证明了，一是比较复杂，二来我也不会，O(∩_∩)O哈哈~）。所以我们要用BFS（宽度优先搜索），然后找到之后就退出搜索，这样可以节省时间。如果直接用DFS的话，一般都会T掉。
那么，怎么找到最短路呢，首先我们可以开一个三维数组d，
d[x][y][z]表示从d[0][0][0]到d[x][y][z]的距离，我们的目标就是求出从
d[0][0][0]到d[a-1][b-1][c-1]的距离。
首先开三个全局数组
int p[maxn][maxn][maxn];//记录地图
int d[maxn][maxn][maxn];//记录距离
int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};
我们先看看DFS怎么写：
void dfs(int x, int y, int z, int dis)
{
for(int i = 0; i < 6; i++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
int z1 = z + dz[i];
if(x1 < 0 || x1 >= a || y1 < 0 || y1 >= b || z1 < 0 || z1 >= c) continue;
if(d[x1][y1][z1] > dis + 1 && p[x1][y1][z1] == 0)
{
d[x1][y1][z1] = dis + 1;
dfs(x1, y1, z1, dis + 1);
}
}
}和之前的差不多，就是把二维改成三维，没有什么本质差别。
怎么把它改成BFS呢？
DFS和BFS的区别无非就是DFS优先遍历较远的状态，而BFS优先遍历附近的状态，BFS更适合于求最短路。
DFS呢，就好像从(0,0,0)走到(1,0,0),然后再走到(2,0,0)......总之就是一直往上走，走到不能走为止。然后在向(0,1,0)->(0,2,0)->(0,3,0)...一直往右走。边走边处理状态
BFS还是从（0,0,0）开始走，但是按定义，处理每个状态的顺序应该是(0 0 0) ->(0 1 0) ->(0 2 0) ->(0 1 1) ->(1 2 0)......
对于这种处理顺序，我们可以用队列来实现。
开始时处理（0,0,0）这个点。
对于它能到的三个点（1,0,0），（0,1,0），（0,0,1），我们虽然走到，但是先不处理，先将之加入队列中。现在（0,0,0）处理完了，将之从队列中删掉。
然后取出队首元素（1,0,0），它能到的三个点是（2,0,0）和（1,1，0）和（1,0,1）。还是先不处理，将之加入队列，但是新进入的元素处于队尾。也就是说，这时候队列中有四个元素，依次为：（0,1,0），（0,0,1），（2,0,0）和（1,1，0）。处理完（1,0,0）后队首的元素为（0,1,0）。这样，就达到了我们的目的，将所有状态按由近及远遍历（或者说按照找到这些状态的顺序来遍历，看你喜欢那种说法o((⊙﹏⊙))o）。
当然了，为了防止超时，对于同一个元素，我们仍然规定只能经过一次。可以证明，对于同一个状态，第二次到达时的距离不会优于第一次（基于同样的原因，这里不给出证明￣□￣｜｜）。具体实现的时候，可以把每一个状态的距离初始化为一个非常大的常数INF。然后每次比较距离长短就可以了。
代码如下：
struct node
{
int x, y, z;
int dis;
};//把状态集成一个结构体
void bfs()
{
queue<node>que;
node k;
k.x = 0;
k.y = 0;
k.z = 0;
k.dis = 0;
que.push(k);
while(!que.empty())
{
k = que.front();
que.pop();
printf("(%d %d %d) ->", k.x, k.y, k.z);
if(k.x == a - 1 && k.y == b - 1 && k.z == c - 1) return;
node u;
for(int i = 0; i < 6; i++)
{
u.x = k.x + dx[i];
u.y = k.y + dy[i];
u.z = k.z + dz[i];
if(u.x < 0 || u.x >= a || u.y < 0 || u.y >= b || u.z < 0 || u.z >= c) continue;
if(d[u.x][u.y][u.z] > k.dis + 1 && p[u.x][u.y][u.z] == 0)
{
d[u.x][u.y][u.z] = k.dis + 1;
u.dis = k.dis + 1;
que.push(u);
}
}
}
}POJ3984（https://vjudge.net/problem/POJ-3984）
题面：
迷宫问题
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 30475 |
|
Accepted: 17526 |
Description
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
题意：中文题，还很短，就不说了吧0.0
思路：和上面那道题一样，不过由于数据量很小，用DFS也能过。
实际上，这道题的主要考点是输出路径，虽然也不难，但对于初学者来说，要将之实现也不是一件容易的事。
唔，只需要在遍历的时候对于每一个状态，记录一下它的前驱状态，然后回溯输出就可以了。
代码：
typedef struct U
{
int x, y, num, t;
}a;//结构体，num代表前驱节点编号，为-1时表示无前驱。
dfs部分（偷个懒(ˉ▽￣～) ）：
void dfs(int n) {
if(u[n].x == 4 && u[n].y == 4)
{
print(n);
return;
}
int k = 1;
for(int i = 0; i < 4; i++)
{
int xi = u[n].x + dx[i];
int yi = u[n].y + dy[i];
if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5 && u[n].t + 1 < t[xi][yi] && s[xi][yi] == 0)
{
while(u[n + k].num != -1) k++;
u[n + k].x = xi;
u[n + k].y = yi;
u[n + k].num = n;
u[n + k].t = u[n].t + 1;
t[xi][yi] = u[n].t + 1;
dfs(n + k);
k++;
}
}
}回溯输出部分：
void print(int i) {
if(u[i].num != -1)
{
print(u[i].num);
}
printf("(%d, %d)\n", u[i].x, u[i].y);
}这样就可以保证从第一个点开始输出，一直输出到最后一个点啦！
AC代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int INF = 10;
const int MAXT = 1000;
int s[INF][INF], t[INF][INF];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
typedef struct U
{
int x, y, num, t;
}a;
a u[INF * INF];
void print(int i) {
if(u[i].num != -1)
{
print(u[i].num);
}
printf("(%d, %d)\n", u[i].x, u[i].y);
}
void dfs(int n) {
if(u[n].x == 4 && u[n].y == 4)
{
print(n);
return;
}
int k = 1;
for(int i = 0; i < 4; i++)
{
int xi = u[n].x + dx[i];
int yi = u[n].y + dy[i];
if(xi >= 0 && xi < 5 && yi >= 0 && yi < 5 && u[n].t + 1 < t[xi][yi] && s[xi][yi] == 0)
{
while(u[n + k].num != -1) k++;
u[n + k].x = xi;
u[n + k].y = yi;
u[n + k].num = n;
u[n + k].t = u[n].t + 1;
t[xi][yi] = u[n].t + 1;
dfs(n + k);
k++;
}
}
}
int main() {
for(int i = 0; i < INF * INF; i++)
{
u[i].num = -1;
}
for(int i = 0; i < INF; i++)
{
for(int j = 0; j < INF; j++)
{
t[i][j] = MAXT;
}
}
for(int i = 0; i < 5; i++)
{
for(int j = 0; j < 5; j++)
{
scanf("%d", &s[i][j]);
}
}
dfs(0);
return 0;
}注：其实本题有个超级简单的写法，直接输出样例的输出就可以了0.0 。这道题只有一组测试数据，而且就是样例。。不知道你怎么想，反正我知道的时候感觉很Σ(⊙▽⊙"a...
小结：怎么说呢，DFS和BFS确实是很基础的一些知识吧，特别是在图论中，经常会用到BFS来处理图。这两个难度也不高，尽量掌握吧╮(╯▽╰)╭..至少保证练习之后至少能独立码出一道题吧0.0
上一篇： php导入大量数据到mysql性能优化