高级搜索

BFS-1: Flood Fill && 最短路¶

(1) flood fill: 线性时间复杂度内, 找到某个点所在的连通块¶

4️连通

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

8连通

C++
for (int i=t.x-1; i<=t.x+1; i++)
    for (int j=t.y-1; j<=t.y+1; j++)
        if (i==t.x && j==t.y) continue;

奇怪的走法 (马的遍历)

C++
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

标配:

struct node {int x, int y;};
bool st[][]; 是否走过
int dist[][]; 距离 (最短路...)
char g[][]; 地形

要规避:

st[i][j] == true: 已经走过的点不能继续走
1. 当一个题目同时要维护diatance时, 就可以不需要再用st[]了, dist[] 可以完美替代 st[] 的角色
g[i][j] == 'X': 障碍物不能走
if (i==t.x && j==t.y) continue;: 8连通的写法里不能经过自己

常见题型:

求连通块的数目
求每个连通块的大小
追踪“最短路”路径: prev[i][j] 记录转移

1097. 池塘计数

求图中 “连通块” 数目

思路: 遍历扫描地形, 只要当前点符合要求, 就对其求连通块

C++
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 1010;

struct node {
    int x, y;
}a[maxn][maxn];

int n, m;
char g[maxn][maxn]; // 地形
int st[maxn][maxn]; // 是否已经做过
int num; // 池塘 (连通块) 数目

void bfs(int start_x, int start_y)
{
    queue<node> q;

    st[start_x][start_y] = true;
    q.push({start_x, start_y});

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x;
        int ty = t.y;

        for (int i=tx-1; i<=tx+1; i++)
        {
            for (int j=ty-1; j<=ty+1; j++)
            {
                // 不能是当前点 (8连通常见)
                if (i==tx && j==ty) continue;
                // 不能出界
                if (i<0 or i>n-1 or j<0 or j>m-1) continue;
                // 不能重复经过 + 地形合法
                if (st[i][j] or g[i][j]=='.') continue;

                st[i][j] = true;
                q.push({i, j});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    // 下标统一从0开始. 因为读入的是一整个string flow
    for (int i=0; i<=n-1; i++)
        cin >> g[i];

    for (int i=0; i<=n-1; i++)
    {
        for (int j=0; j<=m-1; j++)
        {
            // 遍历扫描, 只要当前点符合要求, 就对其求连通块
            if (g[i][j] == 'W' and !st[i][j])
            {
                bfs(i, j);
                num++;
            }
        }
    }

    cout << num <<endl;
    return 0;
}

1098. 城堡问题

求图中 “连通块” 数目 + 连通块的max_area

连通块数目: 全局变量维护
max_area: 每次bfs()返回当前这个连通块的local_area, 然后用全局变量更新max

C++
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 100;

struct node {
    int x, y;
};

// 注意要跟它""东西南北墙"对应
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

int m, n;
int num, max_area;
// max_num全局更新
// max_area作为bfs()返回值, 随遍历更新
int g[maxn][maxn];
int st[maxn][maxn];

int bfs(int sx, int sy)
{
    queue<node> q;

    int local_area = 1;

    st[sx][sy] = true;
    q.push({sx, sy});

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x;
        int ty = t.y;

        for (int i=0; i<4; i++)
        {
            int xx = tx + dx[i];
            int yy = ty + dy[i];
            // 不能出界
            if (xx<1 or xx>m or yy<1 or yy>n) continue;
            // 不能重复
            if (st[xx][yy]) continue;
            // 不能不合法 (有墙就不能走)
            if ( ((g[tx][ty] >> i) & 1) == 1 ) continue;

            st[xx][yy] = true;
            q.push({xx, yy});
            local_area++;
        }
    }

    return local_area;
}

int main()
{
    cin >> m >> n;
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            cin >> g[i][j];
        }
    }

    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (!st[i][j]) {
                num++;
                max_area = max(max_area, bfs(i, j));
            }
        }
    }

    cout << num <<endl;
    cout << max_area <<endl;
    return 0;
}

[!tip] 字符串 / 字符数组读入的差异如 1097, 读的每一行是没有空格的, like W........WW., 因此char[]每次读入 g[i] 一整行

如 1098, 读如的每一行是存在控股的, like 11 6 11 6 3 10 6, 因此每次读入 g[i][j] 单个元素

1106. 山峰和山谷

连通块计数 + 通过边界判定连通块特征

C++
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 1010;

struct node {
    int x, y;
};

int n;
int g[maxn][maxn];  // 地形
int st[maxn][maxn]; // 是否走过
int peak_num, bottom_num;

void bfs(int sx, int sy, bool& has_higher, bool& has_lower)
{
    queue<node> q;

    st[sx][sy] = true;
    q.push({sx, sy});

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x;
        int ty = t.y;

        for (int i=tx-1; i<=tx+1; i++)
        {
            for (int j=ty-1; j<=ty+1; j++)
            {
                // 8连通. 要排除自己
                if (i==tx && j==ty) continue;
                // 不能越界
                if (i<1 or i>n or j<1 or j>n) continue;

                // 边界点: g[tx][ty] != g[i][j]
                if (g[tx][ty] > g[i][j])
                    has_lower = true;
                else if (g[tx][ty] < g[i][j])
                    has_higher = true;
                else // 只有"内部点"才可以继续扩展
                {
                    if (!st[i][j]) {
                        q.push({i, j});
                        st[i][j] = true;
                    }
                }
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin >> g[i][j];

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (!st[i][j])
            {
                bool has_higher = false;
                bool has_lower = false;

                bfs(i, j, has_higher, has_lower);

                if (!has_higher) peak_num++;
                if (!has_lower) bottom_num++;
            }
        }
    }

    cout << peak_num << " " << bottom_num <<endl;
    return 0;
}

(2) 最短路¶

1076. 迷宫问题

左上到右下 + 路径追踪

C++
#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int maxn = 1010;

struct node {
    int x, y;
};

int g[maxn][maxn];
int st[maxn][maxn];
int n;

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

node pre[maxn][maxn]; // 为了记路径转移
stack<node> stk;

void bfs(int sx, int sy)
{
    queue<node> q;

    st[sx][sy] = true;
    q.push({sx, sy});

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x, ty = t.y;

        for (int i=0; i<4; i++)
        {
            int xx = tx + dx[i];
            int yy = ty + dy[i];

            // 不能出界
            if (xx<1 or xx>n or yy<1 or yy>n) continue;
            // 不能重复
            if (st[xx][yy]) continue;
            // 不合法地形
            if (g[xx][yy] == 1) continue;

            st[xx][yy] = true;
            q.push({xx, yy});

            // 记录前驱: (tx, ty) ---1---> (xx, yy)
            pre[xx][yy] = {tx, ty};
        }
    }
}

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin >> g[i][j];

    bfs(1, 1);

    // 把合理的前驱都已经记录下来了
    // (n, n) ---> (1, 1)
    node end = {n, n};
    while (true)
    {
        if (end.x == 1 && end.y == 1) break;

        stk.push({end.x, end.y});
        end = pre[end.x][end.y];
    }
    stk.push({1, 1});

    while (!stk.empty())
    {
        auto t = stk.top();
        stk.pop();
        // 我们是用1-indexed来做的, 题目要求0-indexed
        cout << t.x - 1 << " " << t.y - 1 <<endl;
    }

    return 0;
}

[!tip] 这种记录方案的题目, 一般都不能用vec等来做因为虽然维护好了“我的前缀是谁”，但直接vec输出会导致“很多终点不是(n,n)的路线”也会被输出一般我们会用 stack / queue 等数据结构来维护次序, 并仅仅输出“能到达我们要的终点”的路线

188. 武士风度的牛

马的遍历

C++
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

const int N = 160;

struct node {
    int x, y;
};

int n, m;
int sx, sy, ex, ey;
char g[N][N];    // 地形
int dist[N][N]; // 到起点的最小跳数
int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};

void bfs() 
{
    queue<node> q;
    memset(dist, 0x3f, sizeof dist);

    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x;
        int ty = t.y;

        for (int i = 0; i < 8; i++) 
        {
            int xx = tx + dx[i], yy = ty + dy[i];

            // 不能出界
            if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
            // 不能走过
            if (dist[xx][yy] != 0x3f3f3f3f) continue;
            // 合法地形
            if (g[xx][yy] == '*') continue;

            dist[xx][yy] = dist[tx][ty] + 1;
            q.push({xx, yy});
        }
    }
}

int main() 
{
    cin >> m >> n;

    for (int i=1; i<=n; i++) 
        for (int j=1; j<=m; j++)
            cin >> g[i][j];    

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (g[i][j] == 'K') 
                sx = i, sy = j;
            else if (g[i][j] == 'H')
                ex = i, ey = j;
        }
    }

    bfs();

    cout << dist[ex][ey] <<endl;
    return 0;
}

1100. 抓住那头牛

C++
#include <iostream>
#include <queue>
using namespace std;
typedef pair <int,int> PII;
const int N = 100010;
int st,ed;
int vis[N];
bool check (int x) {
    return x >= 0 && x < N && !vis[x];
}
int bfs () {
    queue <PII> q;
    q.push ({st,0});
    while (!q.empty ()) {
        PII t = q.front ();
        q.pop ();
        int x = t.first,d = t.second;
        if (x == ed) return d;
        if (check (x + 1)) {
            vis[x + 1] = true;
            q.push ({x + 1,d + 1});
        }
        if (check (x - 1)) {
            vis[x - 1] = true;
            q.push ({x - 1,d + 1});
        }
        if (check (x * 2)) {
            vis[x * 2] = true;
            q.push ({x * 2,d + 1});
        }
    }
    return -1;
}
int main () {
    cin >> st >> ed;
    cout << bfs () << endl;
    return 0;
}

BFS-2: 多源BFS && 最短步数模型 && 双端队列BFS¶

(1) 多源BFS¶

很简单, 基于"虚拟原点"原则, 一把全部入队即可 。其他操作跟普通BFS没有任何区别

C++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 1010;

struct node {
    int x, y;
};

char g[maxn][maxn];
int dist[maxn][maxn];
int n, m;

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

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    queue<node> q;

    // 把所有"起点"全部入队 -> 虚拟原点
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    while (!q.empty())
    {
        auto t = q.front();
        q.pop();

        int tx = t.x, ty = t.y;
        for (int i = 0; i < 4; i++)
        {
            int xx = tx + dx[i];
            int yy = ty + dy[i];

            // 不能越界
            if (xx<0 or xx>n-1 or yy<0 or yy>m-1) continue;
            // 不能重复
            if (dist[xx][yy] != 0x3f3f3f3f) continue;

            dist[xx][yy] = dist[tx][ty] + 1;
            q.push({xx, yy});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    // 由于读入方式"没空格", 因此采用一整行读入
    // 同时, 应当采用 0-indexed
    for (int i=0; i<n; i++) cin >> g[i];

    bfs();

    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++) cout << dist[i][j] << " ";
        cout <<endl;
    }

    return 0;
}

(2) 最短步数模型¶

之前提到的所有问题都是在一个“二维棋盘内”，对某个点进行各种操作与观测。

这里我们的“最短步数”，指的是对于棋盘本身而言，经过多少次变换，可以达到一个新的“局面 / 程度”（类比参考 "8数码问题". 基础搜索课）

845. 八数码

第一点：怎么表示一种情况使其能作为节点？

第二点：如何记录每一个状态的“距离”（即需要移动的次数）？

第三点：队列怎么定义，dist数组怎么定义？

解决方法:

将 “3 x 3 矩阵” 转化为 “字符串”

Text Only
// 直接存转化后的字符串
队列可以用 queue<string>

// 将字符串和数字联系在一起，字符串表示状态，数字表示距离
dist数组用 unordered_map<string, int>

C++
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

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

int bfs(string start)
{
    //定义目标状态
    string end = "12345678x";
    //定义队列和dist数组
    queue<string> q;
    unordered_map<string, int> d;
    //初始化队列和dist数组
    q.push(start);
    d[start] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        //记录当前状态的距离，如果是最终状态则返回距离
        int distance = d[t];
        if (t == end) return distance;

        // 查询x在字符串中的下标，然后转换为在矩阵中的坐标
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for (int i = 0; i < 4; i++)
        {
            // 求转移后x的坐标
            int a = x + dx[i], b = y + dy[i];
            // 当前坐标没有越界
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                // 转移x
                swap(t[k], t[a * 3 + b]);
                // 如果当前状态是第一次遍历，记录距离，入队
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                // 还原状态，为下一种转换情况做准备
                swap(t[k], t[a * 3 + b]);
            }
        }
    }

    // 无法转换到目标状态，返回-1
    return -1;
}

int main()
{
    string c, start;

    // 起始棋盘状态
    for (int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;

    return 0;
}

1107. 魔板

其实本质还是很简单的，就是一个“棋盘状态”的最短路问题，但是代码是真难写...

C++
#include <cstring> // 引入cstring头文件，用于字符串操作
#include <iostream> // 引入iostream头文件，用于输入输出流操作
#include <algorithm> // 引入algorithm头文件，用于算法操作
#include <unordered_map> // 引入unordered_map头文件，用于哈希映射操作
#include <queue> // 引入queue头文件，用于队列操作

using namespace std;

char g[2][4]; // 定义一个二维字符数组g，表示状态
unordered_map<string, pair<char, string>> pre; // 定义一个哈希映射pre，存储状态的前驱和移动方式
unordered_map<string, int> dist; // 定义一个哈希映射dist，存储状态的最短距离

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i]; // 将状态的前四个字符赋值给g的第一行
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i]; // 将状态的后四个字符赋值给g的第二行
}

string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i]; // 将g的第一行字符拼接成字符串
    for (int i = 3; i >= 0; i -- ) res += g[1][i]; // 将g的第二行字符逆序拼接成字符串
    return res;
}

string move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]); // 交换g的第一行和第二行的字符
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3]; // 保存g的第一行和第二行的最后一个字符
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1]; // 将g的第一行字符向右移动一位
        g[1][i] = g[1][i - 1]; // 将g的第二行字符向右移动一位
    }
    g[0][0] = v0, g[1][0] = v1; // 将保存的字符放到g的第一行和第二行的第一个位置
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1]; // 保存g的第一行的第二个字符
    g[0][1] = g[1][1]; // 将g的第二行的第二个字符赋值给g的第一行的第二个字符
    g[1][1] = g[1][2]; // 将g的第二行的第三个字符赋值给g的第二行的第二个字符
    g[1][2] = g[0][2]; // 将g的第一行的第三个字符赋值给g的第二行的第三个字符
    g[0][2] = v; // 将保存的字符放到g的第一行的第三个位置
    return get();
}

int bfs(string start, string end)
{
    if (start == end) return 0; // 如果起始状态和目标状态相同，返回0

    queue<string> q; // 定义一个队列q，用于广度优先搜索
    q.push(start); // 将起始状态加入队列
    dist[start] = 0; // 起始状态的最短距离为0

    while (!q.empty())
    {
        auto t = q.front(); // 取出队列的第一个元素
        q.pop(); // 弹出队列的第一个元素

        string m[3]; // 定义一个字符串数组m，存储移动后的状态
        m[0] = move0(t); // 将t进行move0操作得到移动后的状态m[0]
        m[1] = move1(t); // 将t进行move1操作得到移动后的状态m[1]
        m[2] = move2(t); // 将t进行move2操作得到移动后的状态m[2]

        for (int i = 0; i < 3; i ++ )
            if (!dist.count(m[i])) // 如果状态m[i]不在dist中
            {
                dist[m[i]] = dist[t] + 1; // 更新状态m[i]的最短距离
                pre[m[i]] = {'A' + i, t}; // 更新状态m[i]的前驱和移动方式
                q.push(m[i]); // 将状态m[i]加入队列
                if (m[i] == end) return dist[end]; // 如果状态m[i]等于目标状态，返回最短距离
            }
    }

    return -1; // 如果无法到达目标状态，返回-1
}

int main()
{
    int x;
    string start, end;

    for (int i = 0; i < 8; i ++ )
    {
        cin >> x;
        end += char(x + '0'); // 将x转换为字符并添加到end字符串末尾
    }

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i); // 初始化start字符串为"12345678"

    // 每一轮的状态: 棋盘的形态
    // 我们对 "棋盘的形态" 进行BFS搜索, 看看要经过多少步才能转移至终态
    int step = bfs(start, end); // 进行广度优先搜索，得到最短步数

    cout << step << endl; // 输出最短步数

    // 有pre反推出变换序列
    string res;
    while (end != start)
    {
        res += pre[end].first; // 将当前状态的移动方式添加到res字符串末尾
        end = pre[end].second; // 更新当前状态为前驱状态
    }

    reverse(res.begin(), res.end()); // 将res字符串逆序

    if (step > 0) cout << res << endl; // 如果存在最短路径，输出移动方式

    return 0;
}

(3) 双端队列BFS¶

跟一般的BFS只有一点不一样!!!

依然是在队头进行扩展与弹出, 但不同的是:

在从 queue_front 扩展时, 当 queue_head 弹出后, 考察它对应的边权:

边权为0: 插入 queue_front()
边权为1: 插到 queue_tail()

[1] 解决问题:

双端队列主要解决 图中边的权值只有 0 或者 1 的最短路问题

[2] 操作:

每次从队头取出元素，并进行拓展其他元素时

若拓展某一元素的边权是0，则将该元素插入到队头
若拓展某一元素的边权是1，则将该元素插入到队尾

175. 电路维修

与堆优化Dijkstra 一样，必须 在出队时才知道每个点最终的最小值 ，而和一般的bfs不一样，原因是如下图所示:

懒得写了，直接复制题解了...

C++
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = N * N;

int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    deque<PII> q;
    q.push_back({0, 0});

    char cs[] = "\\/\\/";
    /*
    \\: \
    /:  /
    \\: \\
    /:  /
    C++需要对 \ 进行转义
    */
    int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
    int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};

    while (q.size())
    {
        PII t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;

            int ca = t.x + ix[i], cb = t.y + iy[i];
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);

            if (d < dist[a][b])
            {
                dist[a][b] = d;

                if (g[ca][cb] != cs[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }

    return dist[n][m];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

        int t = bfs();

        if (t == 0x3f3f3f3f) puts("NO SOLUTION");
        else printf("%d\n", t);
    }

    return 0;
}

DFS-1: DFS的连通性与搜索顺序¶

(1) DFS连通性

一定可以判定“是否可以找到”，但不确定是不是最短路

内部搜索, 不需要“恢复现场”

1112. 迷宫

C++
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 110;

char g[maxn][maxn];
bool st[maxn][maxn];

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

int n, k;
int ha, la, hb, lb;

bool dfs(int sx, int sy)
{
    if (sx==hb && sy==lb) return true;

    // 我的习惯是: 走到这一步, 立马导致状态改变, 而不是加在循环里
    st[sx][sy] = true;

    for (int i=0; i<4; i++)
    {
        int xx = sx + dx[i];
        int yy = sy + dy[i];
        // 不能出界
        if (xx<0 or xx>=n or yy<0 or yy>=n) continue;
        // 不能重复
        if (st[xx][yy]) continue;
        // 地形合法
        if (g[xx][yy] == '#') continue;

        // 往这个方向可以走到, return true
        if (dfs(xx, yy)) return true;
    }

    // 从当前点四连通没有任何可达终点的路径, return false
    return false;

    // 因此如果需要回溯应该在这个位置
}

int main()
{
    cin >> k;

    while (k--)
    {
        // 初始化clear_all()
        memset(g, 0, sizeof g);
        memset(st, 0, sizeof st);

        cin >> n;
        for (int i=0; i<n; i++) cin >> g[i];
        cin >> ha >> la >> hb >> lb;

        // 特判 起点 && 终点 合法性
        if (g[ha][la]=='#' || g[hb][lb]=='#') 
        {
            puts ("NO");
            continue;
        }

        // dfs 递归
        if (dfs(ha, la)) puts("YES");
        else puts("NO");
    }

    return 0;
}

1113. 红与黑

C++
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 30;

char g[maxn][maxn];
bool st[maxn][maxn];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, 1, -1, 0};

int n, m;
int sx, sy;
int cnt;

void dfs(int x, int y)
{
    // 我的习惯是: 走到这一步, 立马导致状态改变, 而不是加在循环里
    cnt++;
    st[x][y] = true;

    for (int i=0; i<4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];

        // 不能出界
        if (xx<0 or xx>=n or yy<0 or yy>=m) continue;
        // 不能重复
        if (st[xx][yy]) continue;
        // 地形合法
        if (g[xx][yy] == '#') continue;

        dfs(xx, yy);
    }

    // 因此如果需要回溯应该在这个位置
}

int main()
{
    while (cin >> m >> n, m || n)
    {
        // 初始化 clear_all()
        cnt = 0;
        memset(g, 0, sizeof g);
        memset(st, 0, sizeof st);

        // 注意输入是"无空格"的, 因此要采用 g[i] 形式
        // 同时也意味着, 0-indexed
        for (int i=0; i<n; i++) cin >> g[i];

        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++)
                if (g[i][j] == '@') sx = i, sy = j;

        dfs(sx, sy);

        cout << cnt <<endl;
    }

    return 0;
}

842. 排列数字

C++
#include <iostream>
using namespace std;

const int maxn = 10;

int a[maxn];
bool st[maxn];
int n;

void dfs(int x) // 枚举第i位放谁
{
    if (x == n + 1)
    {
        for (int i=1; i<=n; i++) cout << a[i] << " ";
        cout <<endl;

        return;
    }

    for (int i=1; i<=n; i++)
    {
        if (st[i]) continue;

        st[i] = true;
        a[x] = i;

        dfs(x+1);

        // 回溯
        st[i] = false;
        a[x] = 0;
    }
}

int main()
{
    cin >> n;
    dfs(1);

    return 0;
}

843. n-皇后问题

C++
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 11;

char q[N][N]; // 存储棋盘
bool dg[N * 2], udg[N * 2], cor[N]; // 点对应的两个斜线以及列上是否有皇后

int n;

void dfs(int r)
{
    // 出口: "出界的"
    if (r == n+1) // 放满了棋盘，输出棋盘
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++) cout << q[i][j];
            puts("");
        }
        puts("");
        return;
    }

    for (int i = 1; i <= n; i++) // 对于第 r 行, 考察第 i 列 是否放皇后
    {
        if (!cor[i] && !dg[i + r] && !udg[n - i + r]) // 不冲突，放皇后
        {
            q[r][i] = 'Q';
            cor[i] = dg[i + r] = udg[n - i + r] = 1;

            dfs(r + 1);

            // 恢复现场
            cor[i] = dg[i + r] = udg[n - i + r] = 0;
            q[r][i] = '.';
        }
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            q[i][j] = '.';

    dfs(1); // 入口: "合法的"

    return 0;
}

(2) DFS搜索顺序

外部搜索, 需要"恢复现场"

这里我们的重心是: 熟悉一般应该如何设计状态、遍历方式，来让DFS不遗漏地考察每一状态

1116. 马走日

C++
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 20;

bool st[maxn][maxn];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int T;
int n, m;
int cnt;

void dfs(int x, int y, int cur_num)
{
    if (cur_num == n * m) { // 找到一个全遍历方案
        cnt++;
        return;
    }

    // 我的习惯是: 走到这一步, 立马导致状态改变, 而不是加在循环里
    st[x][y] = true;

    for (int i=0; i<8; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];

        // 不能出界
        if (xx<0 or xx>=n or yy<0 or yy>=m) continue;
        // 不能重复
        if (st[xx][yy]) continue;
        // 地形合法
        // pass
        dfs(xx, yy, cur_num + 1);
    }

    // 因此回溯应该在这个位置
    st[x][y] = false;
}

int main()
{
    cin >> T;

    while (T--)
    {
        // 初始化 clear_all()
        int sx, sy;
        memset(st, 0, sizeof st);
        cnt = 0;

        cin >> n >> m >> sx >> sy;

        dfs(sx, sy, 1);

        cout << (cnt ? cnt : 0) <<endl;
    }

    return 0;
}

1117. 单词接龙

字符串替换主串从后向前遍历，子串从前向后，用substr截取，相等就替换然后一直搜下去。

这里有个小技巧

因为他给了开头字母，但是不能替换整个串，所以我们在开头字母前随便补一个字符。

然后丢到dfs里，直接搜到最大值，最后答案减一即可。

C++
#include<iostream>

using namespace std;

const int N = 25;

int n, ans;
string s[N];
int st[N];

void dfs(string x, int y)
{
    st[y] ++;
    int len = x.size();
    ans = max(ans, len);
    string t;
    for(int i = 0; i < n; i ++)
        for(int j = len - 1, k = 1; j > 0 && k < s[i].size(); j --, k ++)
        {
            if(st[i] < 2 && x.substr(j) == s[i].substr(0, k))
            {
                t = x.substr(0, len - k) + s[i];
                dfs(t, i);
            }
        }
    st[y] --;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> s[i];

    string start;
    cin >> start;
    start = " " + start; // 在前面添加一个字符
    dfs(start, n);

    cout << ans - 1 << endl;
}

1118. 分成互质组

C++
#include <iostream>

using namespace std;

const int N = 15;

int n;
int p[N]; // 存放数
int group[N][N]; // 存放每个组
bool st[N]; // 标记每个数是否被放进了组内
int ans; // 当前所存在的最优解

int gcd(int a, int b) { // gcd求最大公约数
    return b ? gcd(b, a % b) : a;
}

bool check(int g[], int gc, int num) { // 判断当前组中的数是否和该数都互质(即该数能否放进该组)
    for (int i = 0; i < gc; ++ i) // 枚举此组组内每个数
        if (gcd(g[i], p[num]) > 1 ) // 只要组内有数和该数不互质了就 return false
            return false;
    return true; // 否则 return true
}

void dfs(int g, int gc, int tc, int start) { 
        // g为当前的最后一组的组的序号, gc为当前组内搜索到的数的序号；
        // tc为当前搜索过的数的数量, start为当前组开始搜索的数的序号

    if (g >= ans) return ; // 如果有比当前最优解所需的组数更多的解法说明此解不为最优解-->直接return即可
    if (tc == n) ans = g; // 如果搜完了所有点了,说明此解为当前的最优解,更新最优解

    bool flag = true; // flag标记是否能新开一组
    for (int i = start; i < n; ++ i) // 枚举每个数
        if (!st[i] && check(group[g], gc, i)) { // 如果当前数还未被放进组里 且 与当前的组中的数都互质
            st[i] = true; // 将该数标记为被放进组里的状态
            group[g][gc] = p[i]; // 将该数放进该组
            dfs(g, gc + 1, tc + 1, i + 1); 
                // 继续搜索该组,组内数的数量gc + 1,总的数的数量tc + 1,搜索的数的序号i + 1
            st[i] = false; // 恢复
            flag = false; // 如果能放进当前最后一组,则不用新开一组,故flag标记为false
        }

    if (flag) dfs(g + 1, 0, tc, 0); 
        // 如果无法放进最后一组,则新开一组来搜索
            // 当前最后一组的组的序号g + 1, 组内搜索的数的序号gc为0；
            // 搜索到的数tc未变, 当前组内开始搜索的数的序号start为0
    /* 此时的dfs操作其实就相当于开了一个组开始搜索的操作,还没有放数进来 */
}

int main() {
    cin >> n;
    ans = n; // 还未搜索时,假定最优解为最坏的情况每个数都分一组

    for (int i = 0; i < n; ++ i) scanf("%d", p + i);

    dfs(1, 0, 0, 0); 
    // 从第一个组g = 1, 组内没有数gc = 0；
    // 还没搜索到点tc = 0, 当前组还未开始遍历数start = 0的初始状态开始搜索

    cout << ans << endl; // 输出搜索完后的最优解

    return 0;
}

DFS-2: 剪枝¶

玄学剪枝的基本策略:

优化搜索顺序
1. 优先搜索 “分支较少” 的节点
排除等效冗余
1. 比如求组合数, (1,2)和(2,1)完全等效, 用set来枚举状态更好
2. 常见的做法是: 让内部顺序保持一致 (比如从小到大)
可行性剪枝
1. 如果在进行过程中就已经发现不可行, 直接 return false
最优性剪枝
1. 如果在逆行过程中就已经发现不可能最优, 直接 return false
记忆化搜索 (DP)

165. 小猫爬山

分析:

代码:

C++
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2e1;

int cat[N], cab[N];
int n, w;
int ans;

bool cmp(int a, int b) {
    return a > b;
}

void dfs(int now, int cnt) {
    if (cnt >= ans) {
        return;
    }
    if (now == n + 1) {
        ans = min(ans, cnt);
        return;
    }
    //尝试分配到已经租用的缆车上
    for (int i = 1; i <= cnt; i++) {  //分配到已租用缆车
        if (cab[i] + cat[now] <= w) {
            cab[i] += cat[now];
            dfs(now + 1, cnt);
            cab[i] -= cat[now];  //还原
        }
    }

    // 新开一辆缆车
    cab[cnt + 1] = cat[now];
    dfs(now + 1, cnt + 1);
    cab[cnt + 1] = 0;
}

int main() 
{
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> cat[i];
    }

    // "优化搜索顺序" 剪枝
    // 优先搜索“分支较少”的节点
    sort(cat + 1, cat + 1 + n, cmp);

    ans = n;

    dfs(1, 0);

    cout << ans << endl;

    return 0;
}

166. 数独

位运算: 很明显这里面check判定很多, 我们必须优化这个check, 所以我们可以对于, 每一行, 每一列, 每一个九宫格, 都利用一个九位二进制数保存,当前还有哪些数字可以填写.

lowbit(x): 我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.

C++
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t;
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if (!cnt) return true;

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (str[i * N + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ )
        for (int j = 0; j < N; j ++ )
            ones[i] += i >> j & 1;

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i ++ )
            for (int j = 0; j < N; j ++, k ++ )
                if (str[k] != '.')
                {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                }
                else cnt ++ ;

        dfs(cnt);

        puts(str);
    }

    return 0;
}

167. 木棒

解析:

DFS 搜索顺序：根据木棒的长度从小到大枚举每根木棒，对于每根木棒，枚举可以由哪些木棍拼成，如果所有的木棍拼成了长度相等的多个木棒，说明找到了答案，否则木棒长度加 1 继续搜索

为什么是正确的？

因为题目要求保证拼凑成功的前提下，还有分组尽可能少，即木棒数量尽可能少，所以我们从小到大枚举每根木棒的长度，第一次找到答案时就是最优解

剪枝优化：（各种优化，非常多）

剪枝 1：sum % length == 0 只有 length 是 sum 的约数才有可能凑出多个等长的木棒
剪枝 2：优化搜索顺序，木棍长度从大到小排序，可以减少搜索的分支排除等效冗余优化
剪枝 3-1：确定每根木棒中木棍的枚举顺序，因为我们的方案和顺序没有关系，以组合的形式枚举方案可以少搜很多重复方案
剪枝 3-2：如果当前木棍没有搜到方案，则跳过所有长度相等的木棍
剪枝 3-3：如果是木棒的第一根木棍就搜索失败了，则一定搜不到方案
剪枝 3-4：如果是木棒的最后一根木棍（+ 上它木棒长度正好是 length）搜索失败了，也一定搜不到方案

证明 3-3：如果在当前木棒 a 的开头换一根木棍 y 可以搜到方案，那么原来这根木棍 x一定在后面的某根木棒 b 中，我们交换木棒 b 的木棍 x 和开头的木棍不会影响答案，那么此时就出现了以木棍 x 开头的木棒搜到了答案，这我们的已知矛盾，所以只要有一根木棒的开头搜不到方案，不管这个位置放哪根木棍都搜不到方案。

证明 3-4：如果我们换几根 / 一根木棍 y 放在当前木棒 a 的最后可以搜到答案，那么原来这跟木棍 x 也一定在后面的某根木棒 b 中，因为 x 和 y 的长度相等，此时把 x 交换过去，此时就出现了以木棍 x 结尾的木棒搜到了答案，这我们的已知矛盾，所以只要有一根木棒的最后一根木棍搜不到方案，不管这个位置放哪根木棍都搜不到方案。

注意：这里有个前提是，当前木棒 + 最后一根木棍的总长度正好是 length，上面证明才成立。

代码:

C++
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=70;

int w[N],sum,length,n;
bool st[N];

bool dfs(int u,int part,int start)//第u组,part第u组的已有长度,start表示第u组的枚举位置;
{
    if(u*length==sum) return true;//如果总长度到达了,返回true
    if(part==length) return dfs(u+1,0,0);//true要一直持续不断的返回,false同理

    for(int i=start;i<=n;i++)
    {
        if(st[i]) continue;
        if(w[i]+part>length) continue;
        st[i]=true;//标记已经使用
        if(dfs(u,w[i]+part,i+1)) return true;//因为前i个棍子都在第u组枚举了,所以直接从第i+1根棍子开始枚举
        st[i]=false;//返回上层分支时要恢复现场(枚举该组不选择第i根根子的方案)

        if(!part||w[i]+part==length) return false;//如果第一根失败了或者最后一根失败了,就一定失败

        int j=i;//如果i失败了,那么长度跟i一样的棍子也一定失败
        while(j<=n&&w[j]==w[i]) j++;
        i=j-1;
    }

    return false;//枚举完了还没有成功,就返回失败
}

int main()
{
    while(cin>>n,n)
    {
        //初始化
        memset(st,0,sizeof st);
        sum=0,length=1;

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
            sum+=w[i];//总和
        }

        //倒着排序,以减少分支
        sort(w+1,w+n+1);
        reverse(w+1,w+n+1);

        while(1)//枚举length的长度
        {
            if(sum%length==0&&dfs(0,0,0))
            {
                printf("%d\n",length);
                break;
            }
            length++;
        }
    }

    return 0;
}

168. 生日蛋糕

C++
#include<iostream>
#include<cmath>
using namespace std;

const int N = 24, INF = 1e9;

int n, m;
int minv[N], mins[N];
int res = INF;

//记录每层的半径和高，因为会用到上一层的高度
int R[N], H[N];

//u当前层次，v当前处理的体积和，s当前处理的面积和
void dfs(int u, int v, int s)
{
    if(v + minv[u] > n) return;
    if(s + mins[u] >= res) return;
    if (s + 2 * (n - v) / R[u + 1] >= res) return;

    if(!u)
    {
        if(v == n) res = s;
        return;
    }

    //搜索顺序，先R后H，从大到小
    for(int r = min(R[u + 1] - 1,(int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--)
        for(int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--)
        {
            H[u] = h, R[u] = r;

            //最底层的时候需要加上r*r
            int t = u == m ? r * r : 0;

            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    //m+1层不存在，作为哨兵，减少边界情况的判断
    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

    if(res == INF) res = 0;
    cout << res << endl;


    return 0;
}