DFS和BFS的实例

• 深度优先搜索的两个实例：

部分和问题

 1 // 输入
 2 int a[MAX_N];
 3 int n, k;
 4 
 5 // 已经从前i项得到了和sum，然后对于i项之后的进行分支
 6 bool dfs(int i, int sum) {
 7     // 如果前n项都计算过了，则返回sum是否与k相等
 8     if (i == n) return sum == k;
 9 
10     // 不加上a[i]的情况
11     if (dfs(i + 1, sum)) return true;
12 
13     // 加上a[i]的情况
14     if (dfs(i + 1, sum + a[i])) return true;
15 
16     // 无论是否加上a[i]都不能凑成k就返回false
17     return false;
18 }
19 
20 void solve() {
21     if (dfs(0, 0)) printf("Yes\n");
22     else printf("No\n");
23 }

Lake Counting

 1 // 输入
 2 int N, M;
 3 char field[MAX_N][MAX_M + 1]; // 园子
 4 
 5 // 现在位置(x,y)
 6 void dfs(int x, int y) {
 7     // 将现在所在位置替换为.
 8     field[x][y]  = '.';
 9 
10     // 循环遍历移动的8个方向
11     for (int dx = -1; dx <= 1; dx++) {
12         for (int dy = -1; dy <= 1; dy++) {
13             // 向x方向移动dx，向y方向移动dy，移动的结果为(nx,ny)
14             int nx = x + dx, ny = y + dy;
15             // 判断(nx,ny)是不是在园子内，以及是否积水
16             if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'w') dfs(nx, ny);
17         }
18     }
19     return ;
20 }
21 
22 void solve() {
23     int res = 0;
24     for (int i = 0; i < N; i++) {
25         for (int j = 0; j < M; j++) {
26             if (field[i][j] == 'W') {
27                 // 从有W的地方开始dfs
28                 dfs(i, j);
29                 res++;
30             }
31         }
32     }
33     printf("%d\n", res);
34 }

• 宽度优先搜索的一个实例：

  迷宫的最短路径

  

 1 const int INF = 100000000;
 2 
 3 // 使用pair表示状态时，使用typedef会更加方便一些
 4 typedef pair<int, int> P;
 5 
 6 // 输入
 7 char maze[MAX_N][MAX_M + 1]; // 表示迷宫的字符串的数组
 8 int N, M;
 9 int sx, sy; // 起点坐标
10 int gx, gy; // 终点坐标
11 
12 int d[MAX_N][MAX_M]; // 到各个位置的最短距离的数组
13 
14 // 4个方向移动的向量
15 int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
16 
17 // 4个方向移动的向量
18 // 如果无法到达， 则时INF
19 int bfs() {
20     queue<P> que;
21     // 把所有的位置都初始化为INF
22     for (int i = 0; i < N; i++)
23         for (int j = 0; j < M; j++) d[i][j] = INF;
24     // 将起点加入队列，并把这一地点的距离设置为0
25     que.push(P(sx, sy));
26     d[sx][sy] = 0;
27 
28     // 不断循环直到队列的长度为0
29     while (que.size()) {
30          // 从队列的最前端取出元素
31          P p = que.front(); que.pop();
32          // 如果取出的状态已经是终点，则结束搜索
33          if (p.first == gx && p.second == gy) break;
34 
35          // 四个方向的循环
36          for (int i = 0; i < 4; i++) {
37             // 移动之后的位置记为(nx, ny)
38             int nx = p.first + dx[i], ny = p.second + dy[i];
39 
40             // 判断是否可以移动以及是否已经访问过（d[nx][ny] != INF即为已经访问过）
41             if (0 <= nx && nx < N && 0 < ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF) {
42                 // 可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离+1
43                 que.push(P(nx, ny));
44                 d[nx][ny] = d[p.first][p.second] + 1;
45             }
46          }
47     }
48     return d[gx][gy];
49 }
50 
51 void solve() {
52     int res = bfs();
53     printf("%d\n", res);
54 }