深度优先搜索

九月 15, 2018 3016

常见算法 / 骗分技巧

洛谷P1605 迷宫

题目地址

DFS 入门题

用一个数组mp存图，vis记录是否经过了这个点

1
2
mp[i][j] = 0 表示有障碍
mp[i][j] = 1 表示没有障碍

用一个函数dfs(x, y)来搜索

1
2
3
当坐标为终点时，直接return，方案数++

如果这个点没被访问过，而且这个点没有障碍，就把这个点设为访问过，然后dfs这个点

要注意的是起始点是访问过的

代码实现：

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

bool vis[6 + 2][6 + 2];
int mp[6 + 2][6 + 2];

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};

int tot, endx, endy, stx, sty, n, m, t;

void dfs(int x, int y) {
    if (x == endx && y == endy) {
        ++tot;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int nowx = x + dx[i];
        int nowy = y + dy[i];
        if (!vis[nowx][nowy] && mp[nowx][nowy]) {
            vis[nowx][nowy] = true;
            dfs(nowx, nowy);
            vis[nowx][nowy] = false;
        }
    }
}

int main(int argc, char *const argv[]) {
    cin >> n >> m >> t;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            mp[i][j] = (int) true;
        }
    }
    cin >> stx >> sty;
    cin >> endx >> endy;
    for (int i = 1; i <= t; ++i) {
        int l, r;
        cin >> l >> r;
        mp[l][r] = false;
    }
    vis[stx][sty] = true;
    dfs(stx, sty);
    cout << tot << endl;
    return 0;
}

洛谷P1162 填涂颜色

题目地址

本来这是一道 BFS 的题

但是有一种玄学的做法可以用 DFS

首先开两个mp存图，输入1时在第一个mp里存1，在第二个mp里存-1

具体就是搜索边界（每一行的第一个和第n个，每一列的第一个和第n个），在搜索的同时更新第一个mp为1

搜索完了就进行判断输出

1
2
3
当第二个mp[i][j]为-1时输出1
否则当第一个mp[i][j]为1时就输出2（被更新过了）
否则输出0

代码实现：

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 30 + 5;

int mp[MAXN][MAXN];
int orz[MAXN][MAXN];
int n;

void dfs(int x, int y) {
    if (x > n || x < 1 || y > n || y < 1 || mp[x][y] != 0) return;
    mp[x][y] = true;
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
}

int main(int argc, char *const argv[]) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == 1) orz[i][j] = -1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (mp[i][1] != 1) dfs(i, 1);
        if (mp[i][n] != 1) dfs(i, n);
    }
    for (int i = 1; i <= n; ++i) {
        if (mp[1][i] != 1) dfs(1, i);
        if (mp[n][i] != 1) dfs(n, i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (orz[i][j] == -1) cout << 1 << ' ';
            else if (mp[i][j] == 0) cout << 2 << ' ';
            else cout << 0 << ' ';
        }
        puts("");
    }
    return 0;
}