【算法基础篇】DFS和BFS及其经典习题

DFS深搜

深搜解决排列问题，也是一个很好的模板

问题

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

AC

#include <iostream>

using namespace std;
const int N = 10;
int path[N];
bool state[N];

int n;

void dfs(int u)
&#123;
    if(u == n)
    &#123;
        for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);
        printf("\n");
    &#125;
    for(int i = 1; i <= n;  i++)
    &#123;
        if(!state[i])
        &#123;
            path[u] = i;
            state[i] = true;
            dfs(u+1);
            state[i] = false;
        &#125;
    &#125;
&#125;

int main()
&#123;   
    cin >> n;
    dfs(0);
    return 0;
&#125;

DFS习题

n皇后问题

AC代码注释讲解超详细

AC代码

/*dfs方法一*/
// #include <iostream>

// using namespace std;
// const int N = 20;
// int n;
// bool col[N], dg[N], udg[N];// 行 对角线 反对角线
// char g[N][N];

// void dfs(int h)
// &#123;
//     if(h == n)
//     &#123;
//         for(int i = 0; i < n; i ++)
//         &#123;
//             for(int j = 0; j < n; j ++)
//                 cout << g[i][j];

//             cout << endl;
//         &#125;
//         cout << endl;
//     &#125;
//     //每一列
//     for (int l = 0; l < n; l ++ )
//     &#123;
//         // 正对角线y =  x + b => b = y - x + n（防止负数）
//         // 反对角线y = -x + b => b = y + x
//         if(!col[l] && !dg[l + h] && !udg[l - h + n])
//         &#123;
//             g[h][l] = 'Q';
//             col[l] = true, dg[l + h] = true, udg[l - h + n] = true;
//             dfs(h + 1);
//             col[l] = false, dg[l + h] = false, udg[l - h + n] = false;
//             g[h][l] = '.';
//         &#125;
//     &#125;
// &#125;

// int main()
// &#123;
//     cin >> n;
//     for(int i = 0; i < n; i ++)
//         for(int j = 0; j < n; j ++)
//             g[i][j] = '.';
//     dfs(0);
//     return 0;
// &#125;

/*dfs方法二 原始方法*/
#include <iostream>

using namespace std;
const int N =  20;
int n;
bool row[N], col[N], dg[N], udg[N];
char g[N][N];

// x表示当前横坐标 y表示纵坐标 s表示已摆放的皇后个数  
void dfs(int x, int y, int s)
&#123;
    //在x行已经y已经走到最右边
    if(y == n)
    &#123;
        x ++; // 选择下一行
        y = 0; // 下一行的第一列开始 
    &#125;

    // 如果已经摆放了n个皇后 证明已经有一个方案 
    if(x == n)
    &#123;
        if(s == n)
        &#123;
            for(int i = 0; i < n; i ++)
                puts(g[i]);
            puts("");
        &#125;
        return ;
    &#125;

    //不放皇后
    dfs(x, y + 1, s);

    //放皇后
    if(!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n])
    &#123;
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] =   udg[y - x + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] =   udg[y - x + n] = false;
        g[x][y] = '.';
    &#125;
&#125;

int main()
&#123;
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            g[i][j] = '.';
    dfs(0, 0, 0);
    return 0;
&#125;

BFS广搜

走迷宫问题

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

AC代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N];
int d[N][N];
PII q[N * N];

int dx[4] = &#123;-1, 0, 1, 0&#125;, dy[4] = &#123;0, 1, 0, -1&#125;;

void bfs()
&#123;
    int hh = 0, tt = 0;
    q[0] = &#123;0, 0&#125;;
    memset(d, -1, sizeof d);
    d[0][0] = 0;
    while(hh <= tt)
    &#123;
        // 从队头取元素
        PII t = q[hh ++];
        for(int i = 0; i < 4; i ++)
        &#123;
            // 尝试四个方向
            int x = t.first + dx[i], y = t.second + dy[i];
            // 如果能走
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            &#123;
                d[x][y] = d[t.first][t.second] + 1;
                q[++ tt] = &#123;x, y&#125;;
            &#125;
        &#125;
    &#125;
&#125;

int main()
&#123;
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> g[i][j];
    bfs();
    cout << d[n - 1][m - 1];   
    return 0;
&#125;