前言

搜索一般来说主要分两种：深度优先搜索（DFS）和广度优先搜索（BFS）

比如说走迷宫，DFS 简单地说就是使用函数递归，先一条路走到底然后再考虑下一条，而 BFS 是从一点出发使用队列并行的往四面八方出发，所有方向是一起走的

正文

用一道例题来理解：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. 从队中取出一个点
  3. 枚举它能前往的点，把这些点入队
  4. 重复 2~3 步

这样子就能数出到所有能去往的点

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
65
66
67
68
69
70
71
72
73
#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;
struct point
{
    int x, y;
} start;

int bfs()
{
    int ans = 0;
    queue<point> q;
    q.push(start); // q
 
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; i++) // 一批一批地处理，每一批都是步数相同的
        {
            point now = q.front();
            q.pop();
            ans++;
            Map[now.x][now.y] = 0;

            for (int j = 0; j < 4; j++)
            {
                int Nx = now.x + dir[j][0];
                int Ny = now.y + dir[j][1];
                if (Nx < 0 || Nx >= n || Ny < 0 || Ny >= m || !Map[Nx][Ny])
                    continue;
                Map[Nx][Ny] = 0;
                q.push({Nx, Ny});
            }
        }
    }
    return ans;
}
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    while (cin >> m >> n)
    {
        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 == '@')
                    start.x = i, start.y = j;
            }

        cout << bfs() << endl;
    }
}

练习题

hdu 1240 Asteroids!

hdu 1240 Asteroids!

模板题，只是变成了三维的

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int dir[6][3] = {
    {0, 1, 0},
    {0, -1, 0},
    {1, 0, 0},
    {-1, 0, 0},
    {0, 0, 1},
    {0, 0, -1}};
struct point
{
    int x, y, z;
} S, T;
bool Map[N][N][N];
int n;

int bfs()
{
    int len = 0;
    queue<point> q;
    q.push(S);
    Map[S.x][S.y][S.z] = true;
    while (!q.empty())
    {

        int size = q.size();
        for (int i = 0; i < size; i++)
        {
            point p = q.front();
            q.pop();
            if (p.x == T.x && p.y == T.y && p.z == T.z)
                return len;
            for (int i = 0; i < 6; i++)
            {
                int x = p.x + dir[i][0];
                int y = p.y + dir[i][1];
                int z = p.z + dir[i][2];
                if (x >= 0 && x < n && y >= 0 && y < n && z >= 0 && z < n && !Map[x][y][z])
                {
                    Map[x][y][z] = true;
                    q.push({x, y, z});
                }
            }
        }
        len++;
    }
    return -1;
}

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

    while (scanf("%*s %d", &n) != EOF)
    {
        memset(Map, 0, sizeof(Map));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                {
                    char c = getchar();
                    while (c != 'O' && c != 'X')
                        c = getchar();

                    if (c == 'X')
                        Map[j][k][i] = true;
                }

        scanf("%d %d %d", &S.x, &S.y, &S.z);
        scanf("%d %d %d", &T.x, &T.y, &T.z);

        int ans = 0;

        if (S.x == T.x && S.y == T.y && S.z == T.z)
            ans = 0;
        else
            ans = bfs();

        if (ans == -1)
            printf("NO ROUTE\n");
        else
            printf("%d %d\n", n, ans);

        scanf("%*s");
    }
}
hdu 4460 Friend Chains

hdu 4460 Friend Chains

这道题还是有坑点的，首先图不能使用临界矩阵来存，会 TLE （我注释的做法）

然后因为英文题目，我一开始直接机翻，There are multiple cases. 给我翻译成 有多种情况 ，搞得我有点看不懂，到了后面一直 WA 才知道这句话是有多组数据的意思，还是我太菜（

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
const int N = 1024;
const int INF = 0x3f3f3f3f;
// bool Map[N][N];
bool vis[N];
int friendsList[N][N], dis[N];
int n, m;

// int bfs(int id)
// {
//     memset(vis, 0, sizeof(vis));
//     queue<int> q;
//     q.push(id);
//     int sum = 0, len = 0;
//     while (!q.empty() && sum != n)
//     {
//         int size = q.size();
//         for (int k = 0; k < size; k++)
//         {
//             int now = q.front();
//             q.pop();
//             if (vis[now])
//                 continue;
//             vis[now] = 1;
//             sum++;
//             for (int i = 0; i < n; i++)
//             {
//                 if (Map[now][i] && !vis[i])
//                 {
//                     q.push(i);
//                 }
//             }
//         }
//         len++;
//     }
//     // for (int i = 0; i < n; i++)
//     // {
//     //     if (!vis[i])
//     //         return -1;
//     // }
//     if (sum != n)
//         return -1;
//     else
//         return len - 1;
// }

int bfs(int start)
{
    fill(vis, vis + n, 0);
    fill(dis, dis + n, INF);
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    dis[start] = 0;
    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = 1; i <= friendsList[now][0]; i++)
        {
            int next = friendsList[now][i];
            if (!vis[next])
            {
                vis[next] = 1;
                dis[next] = dis[now] + 1;
                q.push(next);
            }
        }
    }
    int maxDis = 0;
    for (int i = 0; i < n; i++)
    {
        if (dis[i] == INF)
            return -1;
        maxDis = max(maxDis, dis[i]);
    }
    return maxDis;
}

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

    while (scanf("%d", &n) != EOF)
    {
        if (n == 0)
            continue;

        for (int i = 0; i < n; i++)
        {
            friendsList[i][0] = 0;
        }

        map<string, int> Name2Id;

        for (int i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            Name2Id[s] = i;
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            string s;
            cin >> s;
            int id1 = Name2Id[s];
            cin >> s;
            int id2 = Name2Id[s];
            // Map[id1][id2] = true;
            // Map[id2][id1] = true;
            friendsList[id1][++friendsList[id1][0]] = id2;
            friendsList[id2][++friendsList[id2][0]] = id1;
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            int tmp = bfs(i);
            if (tmp == -1)
            {
                ans = -1;
                break;
            }
            ans = max(ans, tmp);
        }
        printf("%d\n", ans);
    }
}

总结

BFS 的一般框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int bfs(int start)
{
    // 初始化队列和其他存储结构
    // 将起点入列，标记已访问，步数为 0
    while (!q.empty())
    {
        // 取出首元素
        // 检查是否到达终点，可直接返回（某些题目）
        for (枚举找出它能通往的其他元素)
            if (此元素没有处理过或能被更新为更优的解)
            {
                // 标记已访问
                // 记录它们的步数为当前步数 +1
                // 入队
            }
    }
    // 收尾检查（某些题目）并返回结果
}

记录步数的另一种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bfs(int start)
{
    // 初始化队列和其他存储结构
    // 将起点入列，标记已访问
    // 设置当前步数为 0
    while (!q.empty())
    {
        int size = q.size();
        for (循环 size 次) // 一批一批地处理，每一批都是步数相同的
        {
            // 取出首元素
            // 检查是否到达终点，可直接返回（某些题目）
            for (枚举找出它能通往的其他元素)
                if (此元素没有处理过或能被更新为更优的解)
                {
                    // 标记已访问
                    // 入队
                }
        }
        // 步数自增 1
    }
    // 收尾检查（某些题目）并返回结果
}