Aczy156

Algorithm8.2 DFS

[TOC]

dfs

向深递归

  • 传参的确定 => 可以利用好递归调用栈机制
  • 状态的判断 => 递归到每一层之后，所有参数共同组合决定出一个状态，这个状态维护是否重复

[数组一维模版 & 分层] 全排列

https://www.luogu.com.cn/problem/P1706

#include <iostream>
using namespace std;
int n, a[12], vis[12];

void dfs(int l) {
    if (l == n) {
        for (int i = 0; i < n; ++i) printf("%5d", a[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            a[l] = i;vis[i] = 1;
            dfs(l+1);
            vis[i] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}

素数环 & 分层

https://www.luogu.com.cn/problem/UVA524

1、注意是个环结构，所以说起点固定住就行，别的都是重复的

#include <iostream>
using namespace std;
int n, idx, a[18], vis[18];
#include <cmath>

bool isprime(int x) {
//    printf("--- %d\n", x);
    for (int i = 2; i <= sqrt(x); i++) if (x % i == 0) return false;
    return true;
}

void dfs(int l) {
    if (l == n) {
        for (int i = 0; i < n-1; ++i) printf("%d ", a[i]);
        printf("%d\n", a[n-1]);
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i])
            if (l == n - 1) {
                if (isprime(a[0] + i) && isprime(a[l - 1] + i)) {
                    a[l] = i;
                    vis[i] = 1;
                    dfs(l + 1);
                    vis[i] = 0;
                }
            } else {
                if (isprime(a[l - 1] + i)) {
                    a[l] = i;
                    vis[i] = 1;
                    dfs(l + 1);
                    vis[i] = 0;
                }
            }
    }
}

int main() {
    while (~scanf("%d", &n)) {
        if(idx)printf("\n");
        printf("Case %d:\n", ++idx);
        a[0] = 1; vis[1] = 1;
        dfs(1);
    }
    return 0;
}

[图上二维模版 & 特定终点] 深搜不同路径的个数

迷宫-可到达的路径总数：https://www.luogu.com.cn/problem/P1605

题目大意：有障碍，每条路径不能走回头路。问最多有多少条不同的路径可以到达终点。

#include <iostream>
using namespace std;
#define maxn 7
int mp[maxn][maxn], n, m, t, bx, by, ex, ey, tx, ty, dir[4][2] = {{1,  0}, {-1, 0}, {0,  1}, {0,  -1}}, vis[maxn][maxn], ans = 0;

bool check(int x, int y){
    if (x > 0 && x <= n && y > 0 && y <= m && !vis[x][y] && !mp[x][y]) return true;
    return false;
}

void dfs(int x, int y){
    if (x == ex && y == ey) {ans++;return;}
    for (int i = 0; i < 4; ++i) {
        int nx = x+dir[i][0], ny = y+dir[i][1];
        if (check(nx, ny)) {
            vis[nx][ny] = 1;
            dfs(nx, ny);
            vis[nx][ny] = 0;
        }
    }
}

int main() {
    scanf("%d%d%d%d%d%d%d", &n, &m, &t, &bx, &by, &ex, &ey);
    for (int i = 0; i < t; ++i) {
        scanf("%d%d", &tx, &ty);
        mp[tx][ty] = 1;
    }
    vis[bx][by] = 1;
    dfs(bx, by);
    printf("%d\n", ans);

    return 0;
}

图上规则移动

https://www.luogu.com.cn/problem/P1784

1、在图上从左到右走到头，再走下一行的从左到右，知道走到最后的右下角(8,8)

#include <iostream>
using namespace std;
#define maxn 15
int a[maxn][maxn], block[maxn][maxn], col[maxn][maxn], row[maxn][maxn];

int getblock(int x, int y) {
    if (x >= 0 && x <= 2) {
        if (y >= 0 && y <= 2) return 0;
        if (y >= 3 && y <= 5) return 1;
        if (y >= 6 && y <= 8) return 2;
    } else if (x >= 3 && x <= 5) {
        if (y >= 0 && y <= 2) return 3;
        if (y >= 3 && y <= 5) return 4;
        if (y >= 6 && y <= 8) return 5;
    } else {
        if (y >= 0 && y <= 2) return 6;
        if (y >= 3 && y <= 5) return 7;
        if (y >= 6 && y <= 8) return 8;
    }
}

void pr(){
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    exit(0);
}

void dfs(int x, int y) {
    if (a[x][y])
        if (x == 8 && y == 8) pr();
        else if (y == 8) dfs(x+1, 0);
        else dfs(x, y+1);
    else
        for (int j = 1; j <= 9; ++j) {
            if (!block[getblock(x, y)][j] && !col[y][j] && !row[x][j]) {
                block[getblock(x, y)][j] = 1;col[y][j] = 1;row[x][j] = 1;
                a[x][y] = j;
                if (x == 8 && y == 8) pr();
                else if (y == 8) dfs(x+1, 0);
                else dfs(x, y+1);
                block[getblock(x, y)][j] = 0;col[y][j] = 0;row[x][j] = 0;
                a[x][y] = 0;
            }
        }
}

int main() {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            scanf("%d", &a[i][j]);
            block[getblock(i, j)][a[i][j]] = 1;
            col[j][a[i][j]] = 1;
            row[i][a[i][j]] = 1;
        }
    }
    dfs(0, 0);

    return 0;
}

图上 [模版] 联通块数

https://www.luogu.com.cn/problem/P1596

dfs实现 // 用bfs也可以实现，只是不同的搜索策略。

参数：二维坐标系中的横纵坐标x和y

状态：对于横纵坐标中每个点是否都有去到过，用一个vis[][]来维护

#include <iostream>
using namespace std;
#define maxn 105
int n, m, cnt, dir[8][2] = {{1, 0}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}, {0, 1}, {0, -1}};
char a[maxn][maxn];

void dfs(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int nx = x + dir[i][0], ny = y+dir[i][1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 'W') {a[nx][ny] = '.';dfs(nx, ny);}
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", a[i]);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (a[i][j] == 'W') {cnt++;a[i][j] = '.';dfs(i, j); }
    printf("%d\n", cnt);
    return 0;
}
Posted on Feb 1, 2021