还是从走迷宫开始

与 BFS 不同，DFS 非常简单：每当进入一个状态，生产出第一个子状态后，直接函数递归进去，直到走到头，然后回溯回来，再尝试第二个状态

其实就是队列和栈的区别，BFS 是产生一个状态就扔到队列里，DFS 是产生一批状态，先把它们压入栈，然后取一个出来处理

而函数递归就是一种栈，所以 DFS 实际上并不需要专门声明一个栈出来

还是拿最简单的 hdu 1312 Red and Black 来说事

点击查看题目

  • Problem 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)

  • 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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    6 9
    ....#.
    .....#
    ......
    ......
    ......
    ......
    ......
    #@...#
    .#..#.
    11 9
    .#.........
    .#.#######.
    .#.#.....#.
    .#.#.###.#.
    .#.#..@#.#.
    .#.#####.#.
    .#.......#.
    .#########.
    ...........
    11 6
    ..#..#..#..
    ..#..#..#..
    ..#..#..###
    ..#..#..#@.
    ..#..#..#..
    ..#..#..#..
    7 7
    ..#.#..
    ..#.#..
    ###.###
    ...@...
    ###.###
    ..#.#..
    ..#.#..
    0 0

  • Sample Output

    1
    2
    3
    4
    45
    59
    6
    13

简单地说还是走迷宫，遍历所有可能的位置，并且数格子，大概的算法如下

  1. 从当前点开始向四周观望
  2. 枚举它能到达的点，每枚举出来一个就调用第一步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int N = 128, M = 128;
const int dir[4][2] = { // 四方向
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}};

bool Map[N][M];
int n, m, ans;
struct point
{
    int x, y;
} start;

void dfs(point p)
{
    ans++;                      // 计数
    for (int i = 0; i < 4; i++) // 枚举能到达的点
    {
        point np = {p.x + dir[i][0], p.y + dir[i][1]};
        if (np.x < 0 || np.x >= n || np.y < 0 || np.y >= m) // 可行性检查
            continue;
        if (Map[np.x][np.y]) // 可行性检查
        {
            Map[np.x][np.y] = false; // 占领新点
            dfs(np);                 // 从新点继续搜索
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    while (cin >> m >> n)
    {
        ans = 0;
        if (n == 0 && m == 0)
            continue;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                char tmp = getchar();
                while (tmp != '.' && tmp != '#' && tmp != '@')
                    tmp = getchar();

                if (tmp == '.')
                    Map[i][j] = 1;
                else if (tmp == '#')
                    Map[i][j] = 0;
                else if (tmp == '@')
                {
                    Map[i][j] = 0;
                    start.x = i, start.y = j;
                }
            }
        dfs(start);
        cout << ans << endl;
    }
}

回溯状态：八皇后

好！你已经基本知道 DFS 是怎么一回事了，来看一道经典题目：P1219八皇后

点击查看题目

  • 题目描述

    一个如下的 6×66 \times 6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5 来描述，第 ii 个数字表示在第 ii 行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 61\ 2\ 3\ 4\ 5\ 6

列号 2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。

  • 输入格式

    一行一个正整数 nn，表示棋盘是 n×nn \times n 大小的。

  • 输出格式

    前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

  • 样例 #1

    • 样例输入 #1

      1
      6

    • 样例输出 #1

      1
      2
      3
      4
      2 4 6 1 3 5
      3 6 2 5 1 4
      4 1 5 2 6 3
      4

对于这道题，可以按行搜索，在搜索第 nn 行时，尝试在每一列都放，放完记得要做占领标记，然后继续搜索第 n+1n+1 行，回溯回来第 nn 行的时候，先撤销原来的点，再占领新点，然后再继续搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
int a[100], sum, n; // 每行的皇后都在哪一列
bool b[100], c[100], d[100]; //列，对角线占领情况
int print()
{
    int i;
    sum++;
    if (sum <= 3)
    {
        for (i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
}
int search(int i) // 目前搜索到第 i 行
{
    for (int j = 1; j <= n; j++) // 依次尝试所有列能不能放
    {
        // 右对角线上的每个点，横纵坐标之和总相等，左对角线是之差总相等，+7是为了避免负数
        if (!b[j] && !c[i + j] && !d[i - j + 7])
        {
            a[i] = j; //标记本行的第i列放了一个皇后
            // 如果能放，就宣布占领
            b[j] = 1;
            c[i + j] = 1;
            d[i - j + 7] = 1;
            if (i == n) //放满了就去打印这个解
                print();
            else
                search(i + 1); //否则继续放下一行
            // 撤回本次尝试，回溯（把这个皇后从棋盘上拿回手里）
            b[j] = 0;
            c[i + j] = 0;
            d[i - j + 7] = 0;
        }
    }
}
int main()
{
    cin >> n;
    search(1); //从第一行开始
    cout << sum;
}