基础搜索算法_牛客博客

$Fl oo d - F i ll$ 方法

池塘计数

在这里插入图片描述
因为每个点会被访问一次, 算法时间复杂度 $O (nm)$
$df s$ 写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int dx[8] = {
   0, 0, -1, 1, -1, 1, -1, 1};
const int dy[8] = {
   -1, 1, 0, 0, -1, -1, 1, 1};

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

void dfs(int x, int y) {
   
    st[x][y] |=  true;
    for (int i = 0; i < 8; ++i) {
   
        int new_x = x + dx[i], new_y = y + dy[i];
        if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m) continue;
        if (g[new_x][new_y] == '.' || st[new_x][new_y]) continue;
        dfs(new_x, new_y);
    }
}

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

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

    int res = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            if (!st[i][j] && g[i][j] == 'W') dfs(i, j), res++;
        }
    }

    cout << res << '\n';
    return 0;
}

循环队列写法

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N + 5;
const int dx[8] = {
   0, 0, -1, 1, -1, 1, -1, 1};
const int dy[8] = {
   -1, 1, 0, 0, -1, -1, 1, 1};


int n, m;
char g[N][N];
bool st[N][N];
PII q[M];

void bfs(int x, int y) {
   
    int h = 0, t = 0;
    q[t++] = {
   x, y};
    st[x][y] = true;
    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;
        for (int i = 0; i < 8; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
            if (g[new_x][new_y] == '.') continue;
            st[new_x][new_y] = true;
            q[t++] = {
   new_x, new_y};
            if (t == M) t = 0;
        }
    }
}

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

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

    int res = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            if (!st[i][j] && g[i][j] == 'W') bfs(i, j), res++;
        }
    }

    cout << res << '\n';

    return 0;
}

静态队列(需要设置为全局变量, 否则申请栈空间会超时)

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N;
const int dx[8] = {
   0, 0, -1, 1, -1, 1, -1, 1};
const int dy[8] = {
   -1, 1, 0, 0, -1, -1, 1, 1};


int n, m;
char g[N][N];
bool st[N][N];
PII q[M];

void bfs(int x, int y) {
   
    int h = 0, t = -1;
    q[++t] = {
   x, y};
    st[x][y] = true;
    while (h <= t) {
   
        auto [x, y] = q[h++];
        for (int i = 0; i < 8; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
            if (g[new_x][new_y] == '.') continue;
            st[new_x][new_y] = true;
            q[++t] = {
   new_x, new_y};
        }
    }
}

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

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

    int res = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            if (!st[i][j] && g[i][j] == 'W') bfs(i, j), res++;
        }
    }

    cout << res << '\n';

    return 0;
}

城堡问题

在这里插入图片描述
在 $d x$ 方向是行索引, 也就是纵向, 在 $d y$ 方向是列索引, 也就是横向, 并且当前位置 $g (x, y)$ , 假设要向 $i$ 位置扩展, 需要保证 $\& 1} \ne 1$ , 也就是该方向上没有墙壁, 因为每个位置会被考虑一遍, 算法时间复杂度 $O (nm)$

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 60, M = N * N, INF = 0x3f3f3f3f;
const int dx[4] = {
   0, -1, 0,1};
const int dy[4] = {
   -1, 0, 1, 0};

int n, m;
int g[N][N];
bool st[N][N];
PII q[M];

int bfs(int x, int y) {
   
    int h = 0, t = 0;
    q[t++] = {
   x, y};
    st[x][y] = true;

    int cnt = 1;
    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;

        for (int i = 0; i < 4; ++i) {
   
            if (g[x][y] >> i & 1) continue;
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
            st[new_x][new_y] = true;
            cnt++;
            q[t++] = {
   new_x, new_y};
            if (t == M) t = 0;
        }
    }

    return cnt;
}

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

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

    int maxv = -INF, res = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            if (!st[i][j]) {
   
                maxv = max(maxv, bfs(i, j));
                res++;
            }
        }
    }

    cout << res << '\n' << maxv << '\n';
    return 0;
}

山峰和山谷

在这里插入图片描述
传入的参数 $l, h$ 最终计算完有四种情况

$l = 0, h = 0$ , 也就是在计算过程中, 扩展的区域高度都相等, 即可以算作山峰也可以算作山谷
$l = 0, h = 1$ , 扩展的区域要么高度相等, 要么周围的区域高度都是小于该高度的, 是山峰
$l = 1, h = 0$ , 扩展的区域要么高度相等, 要么周围的区域高度都是大于该高度的, 是山谷
$l = 1, r = 1$ , 扩展的区域要么高度相等, 要么周围有大于该区域高度的, 也有小于该区域高度的, 既不是山峰也不是山谷

综上, 如果 $l = 0$ , $c n t (山峰) + 1$ , 如果 $h = 0$ , $c n t (山谷) + 1$ , 算法时间复杂度 $O(n ^ 2)$

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N;
const int dx[8] = {
   0, 0, -1, 1, -1, 1, -1, 1};
const int dy[8] = {
   -1, 1, 0, 0, -1, -1, 1, 1};

int n;
int g[N][N];
bool st[N][N];
PII q[M];

void bfs(int x, int y, bool &is_h, bool &is_l) {
   
    st[x][y] = true;
    int h = 0, t = 0;
    q[t++] = {
   x, y};

    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;
        for (int i = 0; i < 8; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= n) continue;
            if (g[x][y] != g[new_x][new_y]) {
   
                if (g[x][y] < g[new_x][new_y]) is_l = true;
                else is_h = true;
            }
            else if (!st[new_x][new_y]) {
   
                st[new_x][new_y] = true;
                q[t++] = {
   new_x, new_y};
                if (t == M) t = 0;
            }
        }
    }
}


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

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

    int a = 0, b = 0;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < n; ++j) {
   
            if (!st[i][j]) {
   
                bool h = false, l = false;
                bfs(i, j, h, l);
                if (!h) b++;
                if (!l) a++;
            }
        }
    }

    cout << a << ' ' << b << '\n';

    return 0;
}

最短路模型

迷宫问题

在这里插入图片描述

在输出路径的时候需要使用 $P II$ 保存, 而不是使用 $(x, y)$ , 因为会先修改 $y$ , 导致计算的 $x = p a t h [x] [y]$ 的 $y$ 已经被修改了, 导致错误

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N;
const int dx[4] = {
   0, -1, 0, 1}, dy[4] = {
   -1, 0, 1, 0};

int n, g[N][N];
PII path[N][N];
PII q[M];
bool st[N][N];

void bfs() {
   
    int h = 0, t = 0;
    q[t++] = {
   n - 1, n - 1};
    st[n - 1][n - 1] = true;

    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;
        for (int i = 0; i < 4; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= n || st[new_x][new_y]) continue;
            if (g[new_x][new_y]) continue;

            path[new_x][new_y] = {
   x, y};
            st[new_x][new_y] = true;

            if (new_x == 0 && new_y == 0) return;
            q[t++] = {
   new_x, new_y};
            if (t == M) t = 0;
        }
    }
}

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

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

    bfs();
    
    PII u = {
   0, 0};
    while (u.first != n - 1 || u.second != n - 1) {
   
        cout << u.first << ' ' << u.second << '\n';
        u = path[u.first][u.second];
    }
    cout << n - 1 << ' ' << n - 1 << '\n';

    return 0;
}

武士风度的牛

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
const int N = 200, M = N * N;
const int dx[8] = {
   1, 2, 2, 1, -1, -2, -2, -1};
const int dy[8] = {
   2, 1, -1, -2, -2, -1, 1, 2};

int n, m;
char g[N][N];
PII s, e;
PII q[M];
bool st[N][N];
int d[N][N];

int bfs() {
   
    int h = 0, t = 0;
    st[s.first][s.second] = true;
    q[t++] = {
   s.first, s.second};
    memset(d, 0x3f, sizeof d);
    d[s.first][s.second] = 0;

    int cnt = 0;
    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;
        for (int i = 0; i < 8; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
            if (g[new_x][new_y] == '*') continue;

            st[new_x][new_y] = true;
            d[new_x][new_y] = min(d[new_x][new_y], d[x][y] + 1);
            if (new_x == e.first && new_y == e.second) return d[new_x][new_y];

            q[t++] = {
   new_x, new_y};
            if (t == M) t = 0;
        }
    }
    return -1;
}

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

    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            char c;
            cin >> c;
            g[i][j] = c;
            if (c == 'K') s = {
   i, j};
            else if (c == 'H') e = {
   i, j};
        }
    }

    cout << bfs() << '\n';

    return 0;
}

抓住那头牛

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int op[3] = {
   0, 1, 2};

int n, k;
int q[N], d[N];
bool st[N];

int bfs() {
   
    int h = 0, t = 0;
    q[t++] = n;
    st[n] = true;
    memset(d, 0x3f, sizeof d);
    d[n] = 0;

    while (h != t) {
   
        int u = q[h++];
        if (h == N) h = 0;

        for (int i = 0; i < 3; ++i) {
   
            int v;
            if (op[i] == 0) v = u - 1;
            else if (op[i] == 1) v = u + 1;
            else v = 2 * u;

            if (v < 0 || v >= N || st[v]) continue;
            st[v] = true;
            d[v] = min(d[v], d[u] + 1);
            if (v == k) return d[v];
            q[t++] = v;
            if (t == N) t = 0;
        }
    }

    return 0;
}

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

    cin >> n >> k;
    cout << bfs() << '\n';

    return 0;
}

多源 $BFS$

矩阵距离

在这里插入图片描述
题目的意思就是 $1$ 是所有的起点, 计算所有起点到 $0$ 的最短曼哈顿距离, 做法就是将所有 $1$ 节点入队, 并且将其标记为已访问, 然后从这些节点开始向四周扩展, 维护 $d$ 数组记录最短曼哈顿距离

注意将动态的队列空间开到 $\times n$ , 否则会TLE

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N, INF = 0x3f3f3f3f;
const int dx[4] = {
   0, -1, 0, 1}, dy[4] = {
   1, 0, -1, 0};

int n, m;
char g[N][N];
int f[N][N];
PII q[M];
int h = 0, t = 0;

void bfs() {
   
    while (h != t) {
   
        auto [x, y] = q[h++];
        if (h == M) h = 0;

        for (int i = 0; i < 4; ++i) {
   
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m) continue;
            if (f[x][y] + 1 < f[new_x][new_y]) {
   
                f[new_x][new_y] = f[x][y] + 1;
                q[t++] = {
   new_x, new_y};
                if (t == M) t = 0;
            }
        }
    }
}

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

    memset(f, 0x3f, sizeof f);
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            cin >> g[i][j];
            if (g[i][j] == '1') {
   
                q[t++] = {
   i, j};
                f[i][j] = 0;
            }
        }
    }

    bfs();

    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            cout << f[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

最小步数模型

魔板

在这里插入图片描述

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int M = 50000;

struct F {
   
    string s;
    char op;
};
const char op[3] = {
   'A', 'B', 'C'};
const string s = "12348765";

string e;
unordered_map<string, F> fa;
string q[M];
unordered_map<string, int> d;

string move_A(string s) {
   
    string res = s;
    for (int i = 0; i < 4; ++i) swap(res[i], res[i + 4]);
    return res;
}

string move_B(string s) {
   
    string res = s;
    int a = res[3], b = res[7];
    for (int i = 2; i >= 0; --i) res[i + 1] = res[i];
    for (int i = 6; i >= 4; --i) res[i + 1] = res[i];
    res[0] = a, res[4] = b;
    return res;
}

string move_C(string s) {
   
    string res = s;
    int a = s[1], b = s[2], c = s[5], d = s[6];
    res[1] = c;
    res[2] = a;
    res[5] = d;
    res[6] = b;
    return res;
}

int bfs() {
   
    int h = 0, t = 0;
    d[s] = 0;
    q[t++] = s;

    while (h != t) {
   
        string u = q[h++];
        if (h == M) h = 0;

        for (int i = 0; i < 3; ++i) {
   
            string new_s;
            if (i == 0) new_s = move_A(u);
            else if (i == 1) new_s = move_B(u);
            else new_s = move_C(u);

            if (d.count(new_s)) continue;
            d[new_s] = d[u] + 1;
            fa[new_s] = {
   u, op[i]};

            if (new_s == e) return d[new_s];
            q[t++] = new_s;
            if (t == M) t = 0;
        }
    }
    return 0;
}

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

    for (int i = 0; i < 8; ++i) {
   
        int val;
        cin >> val;
        e += val + '0';
    }
    swap(e[4], e[7]), swap(e[5], e[6]);

    int cnt = bfs();
    cout << cnt << '\n';
    if (cnt == 0) return 0;

    string res;
    if (cnt > 0) {
   
        string tmp = e;
        while (tmp != s) {
   
            F f = fa[tmp];
            res += f.op;
            tmp = f.s;
        }
    }

    reverse(res.begin(), res.end());
    cout << res << '\n';
    return 0;
}

双端队列搜索 / 双向 $BFS$ 搜索

电路维修(双端队列广搜)

在这里插入图片描述

图中黄色圈住的相当于花费是 $0$ , 因为不需要旋转就能连通

红色圈住的相当于花费是 $1$ , 因为需要将当前方格中的电线旋转一次

红色位置是电线的坐标, 假设对于当前点 $(x, y)$ 想要计算相邻点的坐标偏移量应该是 $(- 1, - 1), (- 1, 1), (1, 1), (1, - 1)$
计算周围电线的偏移量应该是 $(- 1, - 1), (- 1, 0), (0, 0), (0, - 1)$

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 510, M = N * N, INF = 0x3f3f3f3f;
const int dx1[4] = {
   -1, -1, 1, 1}, dy1[4] = {
   -1, 1, 1, -1};
const int dx2[4] = {
   -1, -1, 0, 0}, dy2[4] = {
   -1, 0, 0, -1};
const char mp[4] = {
   '\\', '/', '\\', '/'};

int n, m;
char g[N][N];
int d[N][N];
bool st[N][N];
deque<PII> q;

void bfs() {
   
    memset(d, 0x3f, sizeof d);
    memset(st, false, sizeof st);
    d[0][0] = 0;
    q.push_back({
   0, 0});

    while (q.size()) {
   
        auto [x, y] = q.front();
        q.pop_front();
        if (st[x][y]) continue;
        st[x][y] = true;
        for (int i = 0; i < 4; ++i) {
   
            int nx = x + dx1[i], ny = y + dy1[i];
            if (nx < 0 || nx > n || ny < 0 || ny > m) continue;

            int px = x + dx2[i], py = y + dy2[i];
            int val = g[px][py] == mp[i] ? 0 : 1;
            if (d[x][y] + val < d[nx][ny]) {
   
                d[nx][ny] = d[x][y] + val;
                val ? q.push_back({
   nx, ny}) : q.push_front({
   nx, ny});
            }
        }
    }
}

void solve() {
   
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            cin >> g[i][j];
        }
    }

    bfs();
    int res = d[n][m];
    if (res == INF) cout << "NO SOLUTION" << '\n';
    else cout << res << '\n';
}


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

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}

字符串变换(双向广搜)

在这里插入图片描述
$T L E$ 的直接暴力搜索写法 $(8/12)$ , 这里有一个点需要注意

因为 $ma p$ 是按照键值对存储的, 并且键是唯一的, 因此不能使用 $ma p$ , 因为一个键可能对应多个值, 只能使用数组

#include <bits/stdc++.h>

using namespace std;

const int MAX_S = 10;

string a, b;
vector<pair<string, string>> mp;
queue<string> q;
unordered_map<string, int> d;

int bfs() {
   
    d[a] = 0;
    q.push(a);

    while (!q.empty()) {
   
        string u = q.front();
        q.pop();

        if (d[u] + 1 > MAX_S) return MAX_S + 1;

        for (int i = 0; i < u.size(); ++i) {
   
            for (auto &[s1, s2] : mp) {
   
                if (u.substr(i, s1.size()) == s1) {
   
                    string new_s = u.substr(0, i) + s2 + u.substr(i + s1.size());

                    if (d.count(new_s)) continue;
                    d[new_s] = d[u] + 1;
                    if (new_s == b) return d[new_s];
                    q.push(new_s);
                }
            }
        }
    }
    return MAX_S + 1;
}

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

    cin >> a >> b;
    string val1, val2;
    while (cin >> val1 >> val2) mp.push_back({
   val1, val2});

    int step = bfs();

    if (step > MAX_S) cout << "NO ANSWER!" << '\n';
    else cout << step << '\n';

    return 0;
}

不要在内层循环中使用分支语句, 因为CPU很难进行内层循环的分支预测, 因此最好的做法就是在传参的时候传入 $d 1, d 2$ 两个, 而不是unordered_map<string, int> &tmp = d == d1 ? d2 : d1;

双向广度搜索写法

#include <bits/stdc++.h>

using namespace std;

const int MAXS = 10;

string a, b;
vector<pair<string, string>> mp1, mp2;
unordered_map<string, int> d1, d2;

bool bfs(queue<string> &q, vector<pair<string, string>> &mp, unordered_map<string, int> &d, unordered_map<string, int> &_d) {
   
    int val = d[q.front()];

    while (q.size() && d[q.front()] == val) {
   
        string s = q.front();
        q.pop();

        for (int i = 0; i < s.size(); ++i) {
   
            for (auto [s1, s2] : mp) {
   
                if (i + s1.size() <= s.size() && s.substr(i, s1.size()) == s1) {
   
                    string new_s = s.substr(0, i) + s2 + s.substr(i + s1.size());
                    if (d.count(new_s)) continue;
                    d[new_s] = d[s] + 1;
                    if (_d.count(new_s)) return true;
                    q.push(new_s);
                }
            }
        }
    }

    return false;
}

int d_bfs() {
   
    if (a == b) return 0;
    queue<string> q1, q2;
    q1.push(a), q2.push(b);
    d1[a] = 0, d2[b] = 0;

    int step = 0;
    while (q1.size() && q2.size()) {
   
        bool val1 = false, val2 = false;
        if (q1.size() < q2.size()) val1 = bfs(q1, mp1, d1, d2);
        else val2 = bfs(q2, mp2, d2, d1);

        step++;
        if (val1 || val2) return step;
        if (step > MAXS) return MAXS + 1;
    }

    return MAXS + 1;
}

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

    cin >> a >> b;
    string val1, val2;
    while (cin >> val1 >> val2) mp1.push_back({
   val1, val2}), mp2.push_back({
   val2, val1});

    int res = d_bfs();
    if (res > MAXS) cout << "NO ANSWER!" << '\n';
    else cout << res << '\n';
    return 0;
}

$A *$ 算法(优化BFS)

第 $K$ 短路

在这里插入图片描述
终点第 $k$ 次出队就代表找到了第 $k$ 短路线
为了加快搜索, 从终点到起点跑 $d ijk s t r a$ 预估出当前位置 $v$ 到终点 $e$ 的最短距离
原图是有向图, 因此预估的距离 $d^{'}$ , 一定严格小于等于真实距离 $d$ , 也就是 $\le d$ , 因此终点到其他点的最短路是可以作为预估函数的

在算法实现中, 如果 $s = e$ , 需要将 $k + 1$ , 因为要求最短路最少包含一条边, $s$ 到 $e$ 的最短路径是 $0$ , 但是没包含任何边, 因此需要 $k + 1$

因为C++中优先队列默认的是大根堆, 如果需要小根堆实际上是greater<>, 因此在写结构体的比较函数的时候, 是大于而不是小于
也就是bool operator> (const F &f) const

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int N = 1010, M = 2e4 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;
struct F {
   
    int est;
    int dis, u;

    bool operator> (const F &f) const {
   
        return est > f.est;
    }
};

int n, m;
int s, e, k;
int h1[N], h2[N], ed[M], ne[M], w[M], idx;
int d[N];

void add(int h[], int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = h[u], w[idx] = val, h[u] = idx++;
}

void dijkstra() {
   
    bool st[N] = {
   0};
    memset(d, 0x3f, sizeof d);
    d[e] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({
   0, e});

    while (q.size()) {
   
        auto [dis, u] = q.top();
        q.pop();

        if (st[u]) continue;
        st[u] = true;

        for (int i = h2[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] < d[v]) {
   
                d[v] = d[u] + w[i];
                q.push({
   d[v], v});
            }
        }
    }
}

int a_star() {
   
    if (d[s] == INF) return -1;
    priority_queue<F, vector<F>, greater<F>> q;
    q.push({
   d[s], 0, s});

    int st[N] = {
   0};
    while (q.size()) {
   
        auto [est, dis, u] = q.top();
        q.pop();
        st[u]++;
        if (st[e] == k) return dis;

        for (int i = h1[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            // 重要剪枝优化
            if (st[v] < k) {
   
                int val1 = dis + w[i];
                int val2 = val1 + d[v];
                q.push({
   val2, val1, v});
            }
        }
    }

    return -1;
}

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

    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, val;
        cin >> u >> v >> val;
        add(h1, u, v, val);
        add(h2, v, u, val);
    }

    cin >> s >> e >> k;
    if (s == e) k++;

    dijkstra();

    cout << a_star() << '\n';
    return 0;
}

如果某个节点已经被 k 条不同的路径访问过，那么从这个节点的第 k+1 条路径出发，不可能构成到终点的第 k 短路

八数码问题

在这里插入图片描述
估价函数 $f$ 等于当前位置字符与目标位置字符的距离, 假设当前字符是 $c$ , int j = c - '1', 目标的位置是 $t$ , 预估距离等于 $\mod 3 - j \mod 3)$ , 也就是预估最少移动的步数, 在优先队列中预估函数作为比较函数

因为水平方向移动 $x$ 不影响逆序数的数量, 垂直方向移动影响的逆序数的数量一定是偶数, 又因为最终结果的逆序数的数量是 $0$ , 因此如果给定的输入的逆序数的数量是奇数, 一定无法到达终点

#include <bits/stdc++.h>

using namespace std;

const char op[4] = {
   'u', 'd', 'l', 'r'};
const int dx[4] = {
   -1, 1, 0, 0}, dy[4] = {
   0, 0, -1, 1};
const string e = "12345678x";

struct F {
   
    string s;
    char c;
};
struct G {
   
    int est;
    string s;

    bool operator> (const G &g) const {
   
        return est > g.est;
    }
};

string s;
unordered_map<string, F> fa;
unordered_map<string, int> d;

int find_x(string &s) {
   
    for (int i = 0; i < s.size(); ++i) {
   
        if (s[i] == 'x') return i;
    }
    return -1;
}

int get(string &s) {
   
    int res = 0;
    for (int i = 0; i < s.size(); ++i) {
   
        char c = s[i];
        if (c == 'x') continue;
        int val = c - '1';
        res += abs(i / 3 - val / 3) + abs(i % 3 - val % 3);
    }
    return res;
}

void a_star() {
   
    priority_queue<G, vector<G>, greater<G>> q;
    q.push({
   get(s), s});
    d[s] = 0;

    while (!q.empty()) {
   
        auto [dis, u] = q.top();
        q.pop();

        int val = find_x(u);
        int x = val / 3, y = val % 3;

        for (int i = 0; i < 4; ++i) {
   
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;

            string new_s = u;
            swap(new_s[val], new_s[nx * 3 + ny]);

            int new_dist = d[u] + 1;

            if (!d.count(new_s) || new_dist < d[new_s]) {
   
                d[new_s] = new_dist;
                fa[new_s] = {
   u, op[i]};
                if (new_s == e) return;
                q.push({
   new_dist + get(new_s), new_s});
            }
        }
    }
}

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

    string tmp;
    for (int i = 0; i < 9; ++i) {
   
        char c;
        cin >> c;
        s += c;
        if (c != 'x') tmp += c;
    }

    int cnt = 0;
    for (int i = 0; i < 8; ++i) {
   
        for (int j = i + 1; j < 8; ++j) {
   
            if (tmp[i] > tmp[j]) cnt++;
        }
    }

    if (cnt & 1) {
   
        cout << "unsolvable" << '\n';
        return 0;
    }

    a_star();

    string res;
    tmp = e;
    while (tmp != s) {
   
        F f = fa[tmp];
        res += f.c;
        tmp = f.s;
    }
    reverse(res.begin(), res.end());

    cout << res << '\n';

    return 0;
}

DFS搜索

迷宫问题

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

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

int T;
int n;
char g[N][N];
int sx, sy, ex, ey;
bool st[N][N];

bool dfs(int x, int y) {
   
    st[x][y] = true;
    if (x == ex && y == ey) return true;
    for (int i = 0; i < 4; ++i) {
   
        int new_x = x + dx[i], new_y = y + dy[i];
        if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= n || st[new_x][new_y]) continue;
        if (g[new_x][new_y] == '#') continue;
        if (dfs(new_x, new_y)) return true;
    }
    return false;
}

void solve() {
   
    memset(st, false, sizeof st);
    cin >> n;
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < n; ++j) {
   
            cin >> g[i][j];
        }
    }

    cin >> sx >> sy >> ex >> ey;
    if (g[sx][sy] == '#' || g[ex][ey] == '#') {
   
        cout << "NO" << '\n';
        return;
    }
    cout << (dfs(sx, sy) ? "YES" : "NO") << '\n';
}

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

    cin >> T;
    while (T--) solve();

    return 0;
}

红与黑

在这里插入图片描述
全局变量统计

#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y;
char g[N][N];
bool st[N][N];
int res;

void dfs(int x, int y) {
   
    res++;
    st[x][y] = true;
    for (int i = 0; i < 4; ++i) {
   
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
        if (g[new_x][new_y] == '#') continue;
        dfs(new_x, new_y);
    }
}

void solve() {
   
    res = 0;
    memset(st, false, sizeof st);
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            cin >> g[i][j];
            if (g[i][j] == '@') x = i, y = j;
        }
    }

    dfs(x, y);

    cout << res << '\n';
}

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

    while (cin >> m >> n, n || m) solve();

    return 0;
}

局部变量统计

#include <bits/stdc++.h>

using namespace std;

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

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

int dfs(int x, int y) {
   
    int cnt = 1;
    st[x][y] = true;
    for (int i = 0; i < 4; ++i) {
   
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
        if (g[new_x][new_y] == '#') continue;
        cnt += dfs(new_x, new_y);
    }
    return cnt;
}

void solve() {
   
    memset(st, false, sizeof st);
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < m; ++j) {
   
            cin >> g[i][j];
            if (g[i][j] == '@') x = i, y = j;
        }
    }

    cout << dfs(x, y) << '\n';
}

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

    while (cin >> m >> n, n || m) solve();

    return 0;
}

经典问题之马走日

在这里插入图片描述
从当前位置遍历棋盘上所有的点, 问路径数量, 因为棋盘大小是 $\times M$ , 最大不会超过 $81$ , 算法时间复杂度 $O(8 ^ {nm})$ , 因为有回溯剪枝, 时间复杂度比实际要小得多

#include <bits/stdc++.h>

using namespace std;

const int dx[8] = {
   1,-1,2,-2,1,-1,2,-2},dy[8] = {
   2,2,1,1,-2,-2,-1,-1};
const int N = 10;

int T;
int n, m, x, y;
bool st[N][N];
int res;

void dfs(int x, int y, int t) {
   
    if (t == n * m) {
   
        res++;
        return;
    }

    for (int i = 0; i < 8; ++i) {
   
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || st[new_x][new_y]) continue;
        st[new_x][new_y] = true;
        dfs(new_x, new_y, t + 1);
        st[new_x][new_y] = false;
    }
}

void solve () {
   
    memset(st, false, sizeof st);
    res = 0;
    cin >> n >> m >> x >> y;
    st[x][y] = true;
    
    dfs(x, y, 1);
    cout << res << '\n';
}

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

    cin >> T;
    while (T--) solve();

    return 0;
}

单词接龙

在这里插入图片描述

非常关键的剪枝优化: 因为求的是最长的字符串, 因此需要预处理最短前后缀长度

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n;
string s[N];
char c;
int d[N][N];
int ans = 0;
int st[N];

void dfs(string u, int last) {
   
    ans = max(ans, (int) u.size());
    st[last]++;
    for (int i = 0; i < n; ++i) {
   
        if (d[last][i] && st[i] < 2) {
   
            dfs(u + s[i].substr(d[last][i]), i);
        }
    }
    st[last]--;
}


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

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

    // 因为要求生成的字符串长度最长, 预处理最短前后缀
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < n; ++j) {
   
            for (int k = 1; k < min(s[i].size(), s[j].size()); ++k) {
   
                if (s[i].substr(s[i].size() - k) == s[j].substr(0, k)) {
   
                    d[i][j] = k;
                    break;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
   
        if (s[i][0] == c) dfs(s[i], i);
    }

    cout << ans << '\n';
    return 0;
}

分为互质组

在这里插入图片描述
因为数据范围只有 $10$ , 因此可以进行 $df s$ , 因为每个数字可以选择加入已有的组或者新建一个组
对于当前数字 $n$ , 有 $n$ 个选择

元素 $1$ 只有一种选择
元素 $2$ 两种选择, 加入组 $1$ , 或者创建新的组
元素 $3$ 三种选择, 加入组 $1$ , 或者 $2$ , 或者创建新的组
直到元素 $n$ , 有 $n$ 中选择

因此总的状态空间是 $n!$
还要检查组内的互质情况, 整体的算法时间复杂度 $\cdot n!)$

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n, w[N];
vector<int> f[N];
int ans;

int gcd(int a, int b) {
   
    return b ? gcd(b, a % b) : a;
}

bool check(int a, int b) {
   
    if (gcd(a, b) == 1) return true;
    return false;
}

void dfs(int u, int cnt) {
   
    if (cnt >= ans) return;
    if (u == n) {
   
        ans = min(ans, cnt);
        return;
    }

    // 尝试加入已有的组
    for (int i = 0; i < cnt; ++i) {
   
        bool flag = true;
        for (int j = 0; j < f[i].size(); ++j) {
   
            if (!check(w[u], f[i][j])) {
   
                flag = false;
                break;
            }
        }
        if (flag) {
   
            f[i].push_back(w[u]);
            dfs(u + 1, cnt);
            f[i].pop_back();
        }
    }

    // 尝试加入新的组
    f[cnt++].push_back(w[u]);
    dfs(u + 1, cnt);
    f[--cnt].pop_back();
}


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

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    ans = n;
    dfs(0, 0);

    cout << ans << '\n';

    return 0;
}

DFS剪枝优化

小猫爬山

在这里插入图片描述
也就是计算最少多少辆缆车能运输所有的小猫

最优性剪枝: 如果当前计算的缆车数量已经 $\ge$ 已经计算出的最小数量, 那么返回✅
排除等效冗余: 因为每个小猫只会被考虑一次, 没有冗余计算情况, 不需要该剪枝❌
可行性剪枝: 如果当前缆车的重量 $w_i \ge k$ , 当前猫不能放入当前缆车✅
优化搜索顺序: 可以先将小猫按照重量从大到小排序, 先安排大重量的小猫, 这样分支会变少✅

理论算法时间复杂度 $O (n!)$ , 添加剪枝后效率会高很多

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int N = 20;

int n, k;
int w[N];
int res;
int f[N];

void dfs(int u, int cnt) {
   
    if (cnt >= res) return;
    if (u == n) {
   
        res = min(res, cnt);
        return;
    }

    for (int i = 0; i < cnt; ++i) {
   
        if (f[i] + w[u] > k) continue;
        f[i] += w[u];
        dfs(u + 1, cnt);
        f[i] -= w[u];
    }

    f[cnt++] = w[u];
    dfs(u + 1, cnt);
    f[--cnt] -= w[u];
}

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

    cin >> n >> k;
    res = n;
    for (int i = 0; i < n; ++i) cin >> w[i];
    sort(w, w + n, greater<int>());

    dfs(0, 0);

    cout << res << '\n';
    return 0;
}

数独

在这里插入图片描述

优化搜索顺序: 优先摆放剩余数量较少的位置✅
排除等效冗余: 因为每次选择数量较少的位置, 搜索顺序就是确实下来的, 因此不存在冗余计算, 不需要进行剪枝❌
可行性剪枝: 行, 列, 九宫格不能有重复的数字✅
最优性剪枝: 因为不是最优化问题, 因此无法剪枝❌

可以使用位运算优化表示行, 列, 九宫格的数字使用情况

$l o w bi t$ 运算优化

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

int mp[M], bit_cnt[M];
char g[N * N];
int r[N], c[N], cell[3][3];

void init() {
   
    for (int i = 0; i < N; ++i) mp[1 << i] = i;
    for (int i = 0; i < 1 << N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            bit_cnt[i] += i >> j & 1;
        }
    }
}

void draw(int x, int y, int t, bool flag) {
   
    g[x * N + y] = flag ? t + '1' : '.';
    int val = 1 << t;
    if (!flag) val = -val;
    r[x] -= val;
    c[y] -= val;
    cell[x / 3][y / 3] -= val;
}

int calc(int x, int y) {
   
    return r[x] & c[y] & cell[x / 3][y / 3];
}

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

bool dfs(int cnt) {
   
    if (cnt == 0) return true;

    int x, y, min_s;
    int min_cnt = N;

    for (int i = 0; i < N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            if (g[i * N + j] == '.') {
   
                int s = calc(i, j);
                if (bit_cnt[s] < min_cnt) {
   
                    x = i, y = j;
                    min_s = s;
                    min_cnt = bit_cnt[s];
                }
            }
        }
    }

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

    return false;
}


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

    init();

    while (cin >> g, g[0] != 'e') {
   
        for (int i = 0; i < N; ++i) r[i] = c[i] = M - 1;
        for (int i = 0; i < 3; ++i) {
   
            for (int j = 0; j < 3; ++j) {
   
                cell[i][j] = M - 1;
            }
        }

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

        dfs(cnt);

        for (int i = 0; i < N * N; ++i) cout << g[i];
        cout << '\n';
    }

    return 0;
}

非 $l o w bi t$ 运算, 传统位运算

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

int mp[M], bit_cnt[M];
char g[N * N];
int r[N], c[N], cell[3][3];

void init() {
   
    for (int i = 0; i < N; ++i) mp[1 << i] = i;
    for (int i = 0; i < 1 << N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            bit_cnt[i] += i >> j & 1;
        }
    }
}

void draw(int x, int y, int t, bool flag) {
   
    g[x * N + y] = flag ? t + '1' : '.';
    int val = 1 << t;
    if (!flag) val = -val;
    r[x] -= val;
    c[y] -= val;
    cell[x / 3][y / 3] -= val;
}

int calc(int x, int y) {
   
    return r[x] & c[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt) {
   
    if (cnt == 0) return true;

    int x, y, min_s;
    int min_cnt = N;

    for (int i = 0; i < N; ++i) {
   
        for (int j = 0; j < N; ++j) {
   
            if (g[i * N + j] == '.') {
   
                int s = calc(i, j);
                if (bit_cnt[s] < min_cnt) {
   
                    x = i, y = j;
                    min_s = s;
                    min_cnt = bit_cnt[s];
                }
            }
        }
    }

    for (int i = 0; i < N; ++i) {
   
        if (min_s >> i & 1) {
   
            int t = mp[1 << i];
            draw(x, y, t, true);
            if (dfs(cnt - 1)) return true;
            draw(x, y, t, false);
        }
    }
    return false;
}


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

    init();

    while (cin >> g, g[0] != 'e') {
   
        for (int i = 0; i < N; ++i) r[i] = c[i] = M - 1;
        for (int i = 0; i < 3; ++i) {
   
            for (int j = 0; j < 3; ++j) {
   
                cell[i][j] = M - 1;
            }
        }

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

        dfs(cnt);

        for (int i = 0; i < N * N; ++i) cout << g[i];
        cout << '\n';
    }

    return 0;
}

木棒

在这里插入图片描述

可行性剪枝: 假设所有木棍的长度之和是 $s u m$ , 那么当前 $\mod len = 0$ 的时候, 计算是否可以将所有的木棍都拼成木棒✅
优化搜索顺序: 先枚举较长的木棍, 从大到小枚举木棍长度✅
排除等效冗余:✅
1. 在一个木棒的内部, 顺序是无所谓的, 因此在枚举的过程中应该按照组合方式枚举, 也就是木棍编号从小到达枚举
2. 假设放置 $i$ 木棍失效, 那么放置长度相等的木棍 $j$ 也失效(反证法)
假设当前位置放置木棍 $j$ , 是合法的方案, 并且当前位置放置木棍 $i$ 是非法的, 那么因为 $i$ 一定要放置, 假设放置在了 $n$ 号木棒, 可以将这两段进行交换, 结果是矛盾的, 因此假设放置 $i$ 木棍失效, 放置长度相等的木棍 $j$ 也失效
1. 假设木棒的第一个木棍放置失败, 那么该方案失败(反证法)
2. 木棒在最后一个位置失败, 该方案失败(反证法)
最优性剪枝: 无❌

#include <bits/stdc++.h>
#define x first
#define y second

const int N = 70;

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

using namespace std;

bool dfs(int u, int cnt, int curr) {
   
    if (cnt * len == sum) return true;
    if (curr == len) return dfs(0, cnt + 1, 0);
    
    for (int i = u; i < n; ++i) {
   
        if (st[i] || curr + w[i] > len) continue;
        st[i] = true;
        if (dfs(i + 1, cnt, curr + w[i])) return true;
        st[i] = false;
        
        if (curr == 0 || curr + w[i] == len) return false;
        int j = i;
        while (j < n && w[j] == w[i]) j++;
        i = j - 1;
    }
    
    return false;
}

void solve() {
   
    memset(st, 0, sizeof st);
    sum = 0;
    for (int i = 0; i < n; ++i) cin >> w[i], sum += w[i];
    
    sort(w, w + n, greater<int>());
    for (len = 1; ; ++len) {
   
        if (sum % len == 0) {
   
            if (dfs(0, 0, 0)) {
   
                cout << len << '\n';
                break;
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    while (cin >> n, n) solve();

    return 0;
}

生日蛋糕**

在这里插入图片描述
观察得到表面积的计算公式是 $S_{b} + \sum_{i = 0} ^ m 2\pi R_iH_i$ , 其中 $S_b = \pi R_m ^ 2$
体积计算公式 $\sum_{i = 0} ^ m \pi R_i ^ 2H_i$

优化搜索顺序:
1. 从下向上枚举, 因为下面的圆柱占用的体积更大, 分支更少
2. 优先枚举 $r$ , 再枚举 $h$ , 因为对于体积的影响, $r$ 是平方级别的
可行性剪枝: 因为 $R_{i + 1} > R_i$ 并且 $H_{i + 1} > H_i$ , 因此 $R_i$ 和 $H_i$ 的最小值是 $i$ , 假设总的体积是 $V$ , 从 $m$ 到 $i$ 已经使用的体积是 $V^{'}$ , 剩余层所需要的最小体积是 $f [i - 1]$ 那么有不等式 $\pi R_i ^ 2 H_i \le V - V' - f_{i - 1}$ , 将 $H_i$ 取 $i$ (这里是因为先枚举 $R_i$ , 因为 $H_i \ge i$ , 因此是合法的), 得到 $R_i \le \sqrt {\frac{V - V' - f_{i - 1}}{i}}$ , 因此 $R_i$ 的范围是 $\le R_i \le \min(\sqrt {\frac{V - V' - f_{i - 1}}{i}}, R_{i + 1} - 1)$
因为得到了 $R_i$ , 同理 $H_i$ 的范围是
$\le H_i \le \min(\frac{V - V' - f_{i - 1}}{R_i ^ 2}, H_{i + 1} - 1)$
表面积和体积公式的推导剪枝:
第 $1$ 层到 $u$ 层的表面积 $\sum _{i = 1} ^ u2R_iH_i = \frac{2}{R_{u + 1}}\sum_{i = 0} ^ uR_{u + 1}R_iH_i > \frac{2}{R_{u + 1}}\sum_{i = 0} ^ uR_i ^ 2H_i$
第 $1$ 层到 $u$ 层的体积公式 $\sum _{i = 1} ^ {u} R_i ^ 2H_i$
因此有 $\frac{2(V - V')}{R_{u + 1}}$ , 也就是说实际的表面积最小值一定严格大于 $\frac{2(V - V')}{R_{u + 1}}$ , 假设当前累计的表面积是 $S^{'}$ , $\frac{2(V - V')}{R_{u + 1}} \ge res$ , 可行性剪枝
最优性剪枝, 假设当前 $i$ 层数已经累积了表面积 $S$ , 从 $0$ 到 $i - 1$ 的最小表面积是 $g_{i - 1}$ , 当 $S + g_{i - 1} > res$ , 不需要进行搜索

因为未优化搜索顺序导致的超时代码

#include <bits/stdc++.h>

using namespace std;

const int M = 30, INF = 0x3f3f3f3f;

int n, m;
int minv[M], mins[M];
int r[M], h[M];
int res = INF;

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 == 0) {
   
        if (v == n) {
   
            res = min(res, s);
        }
        return;
    }

    int curr_v = n - v - minv[u - 1];

    for (int i = u; i <= min(r[u + 1] - 1, (int) sqrt(curr_v / u)); ++i) {
   
        for (int j = u; j <= min(h[u + 1] - 1, curr_v / i / i); ++j) {
   
            r[u] = i;
            h[u] = j;
            int tmp = u == m ? i * i : 0;
            dfs(u - 1, v + i * i * j, s + 2 * i * j + tmp);
        }
    }
}

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

    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;
    }

    r[m + 1] = h[m + 1] = INF;
    dfs(m, 0, 0);

    if (res == INF) res = 0;
    cout << res << '\n';

    return 0;
}

优化搜索顺序后的代码( $A C$ 代码)

#include <bits/stdc++.h>

using namespace std;

const int N = 30, INF = 0x3f3f3f3f;

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

void init() {
   
    for (int i = 1; i <= m; ++i) {
   
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }
    r[m + 1] = h[m + 1] = INF;
}

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 == 0) {
   
        if (v == n) res = min(res, s);
        return;
    }

    int curr_v = n - v - minv[u - 1];
    for (int i = min(r[u + 1] - 1, (int) sqrt(curr_v / u)); i >= u; --i) {
   
        for (int j = min(h[u + 1] - 1, curr_v / i / i); j >= u; --j) {
   
            r[u] = i;
            h[u] = j;
            int val = u == m ? i * i : 0;
            dfs(u - 1, v + i * i * j, s + 2 * i * j + val);
        }
    }
}

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

    cin >> n >> m;
    init();

    dfs(m, 0, 0);

    if (res == INF) res = 0;
    cout << res << '\n';
    return 0;
}

双向DFS

送礼物

在这里插入图片描述
错误的贪心做法, 直觉做法是先取大重量的物品, 但是因为没有限制物品的次数, 可能小重量无拼凑出来的重量大于一件大物品凑出来的重量, 因此是错误的!!!

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 50;

LL maxv, n;
LL w[N];

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

    cin >> maxv >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    sort(w, w + n, greater<int>());

    LL tmp = maxv;
    for (int i = 0; i < n; ++i) {
   
        if (tmp >= w[i]) tmp -= w[i];
    }

    if (tmp == 0) cout << maxv << '\n';
    else cout << maxv - tmp << '\n';

    return 0;
}

$01$ 背包问题也是错误的, 因为算法时间复杂度是 $\times M)$ , 但是这里的重量是 $2 ^ {31} - 1$ 级别, 空间会爆炸

只能进行暴搜, 物品的数量是 $46$ , 算法时间复杂度 $O(2 ^ {46})$ , 还是需要进行剪枝优化

空间换时间, 预处理前一半, 在处理后一半的时候可以查表前面
将整个数据分为两段
在这里插入图片描述
假设前面的集合是 $S$ , 后面的集合是 $S^{'}$ , 对于后面集合的元素 $a$ , 希望在前面集合中找到一个元素 $b$ , 使得 $\le w$ , 也就是 $\le w - a$ , 在集合 $S$ 中找到 $\le w- a$ 最大的数, 可以使用二分计算
算法时间复杂度 ${\frac{N}{2}} + 2 ^ {\frac{N}{2}}\log ^ {\frac{N}{2}})$

假设前面的系数是 $k$ , $\times k$ , 尝试均摊前后复杂度 $\times k$ , 令 $k = 2 ^ {log _{2} ^ k}$ , $2 ^ k = 2 ^ {N - k + \log_{2} ^ k}$ , 也就是说 $\frac{\log_{2} ^ {k}}{2} = \frac{N}{2}$ 的情况下, 时间均摊情况最优

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 50, M = 25;

int m, n, k;
int w[N];
LL s[1 << M];
int cnt, r_cnt;
LL ans = 0;

void dfs1(int u, LL curr) {
   
    if (u == k) {
   
        s[cnt++] = curr;
        return;
    }

    dfs1(u + 1, curr);
    if ((LL) curr + w[u] <= m) dfs1(u + 1, curr + w[u]);
}

int find(LL x) {
   
    int l = 0, r = r_cnt - 1;
    while (l < r) {
   
        int mid = l + r + 1 >> 1;
        if (s[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

void dfs2(int u, LL curr) {
   
    if (u == n) {
   
        LL val = s[find(m - curr)];
        ans = max(ans, (LL) val + curr);
        return;
    }

    dfs2(u + 1, curr);
    if (curr + w[u] <= m) dfs2(u + 1, curr + w[u]);
}

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

    cin >> m >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];
    sort(w, w + n, greater<int>());

    k = n / 2;
    if (k == 0) k = 1;

    dfs1(0, 0);
    sort(s, s + cnt);

    r_cnt = 1;
    for (int i = 1; i < cnt; ++i) {
   
        if (s[i] == s[r_cnt - 1]) continue;
        s[r_cnt++] = s[i];
    }
    dfs2(k, 0);

    cout << ans << '\n';
    return 0;
}

去重算法实现

    n_cnt = 1;
    for (int i = 1; i < cnt; ++i) {
   
        if (s[i] == s[n_cnt - 1]) continue;
        s[n_cnt++] = s[i];
    }

迭代加深搜索

加成序列

在这里插入图片描述
因为有 $100$ 个数字, 如果直接暴力搜索是 $2 ^ n$ 时间复杂度, 无法通过
迭代加深搜索适用于某些子树的深度很深, 但是答案的子树(搜索树)很浅的情况
通过限制递归的深度实现

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int ans[N];

bool dfs(int u, int k) {
   
    if (u == k) return ans[u - 1] == n;

    // 对于当前层来说, 因为w[i] + w[j]的结果可能是一样的, 因此st用来判重
    bool st[N] = {
   0};
    // 优化搜索顺序
    for (int i = u - 1; i >= 0; --i) {
   
        for (int j = i; j >= 0; --j) {
   
            int s = ans[i] + ans[j];
            if (s > n || s <= ans[u - 1] || st[s]) continue;
            st[s] = true;
            ans[u] = s;
            if (dfs(u + 1, k)) return true;
            st[s] = false;
        }
    }
    return false;
}

void solve() {
   
    memset(ans, 0, sizeof ans);
    ans[0] = 1;
    for (int k = 1; ; ++k) {
   
        if (dfs(1, k)) {
   
            for (int i = 0; i < k; ++i) cout << ans[i] << ' ';
            cout << '\n';
            break;
        }
    }
}

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

    while (cin >> n, n) solve();

    return 0;
}

$I D A *$ 算法

排书问题

在这里插入图片描述
$I D A *$ 算法本质就是迭代加深搜索 + 启发式剪枝

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int T;
int n, w[N];
int m[5][N];

int get() {
   
    int cnt = 0;
    for (int i = 1; i < n; ++i) {
   
        if (w[i] != w[i - 1] + 1) cnt++;
    }
    return (cnt + 2) / 3;
}

bool dfs(int u, int max_dep) {
   
    if (u + get() > max_dep) return false;
    if (get() == 0) return true;

    for (int len = 0; len < n; ++len) {
   
        for (int i = 0; i + len - 1 < n; ++i) {
   
            int j = i + len - 1;

            // 尝试将i~j的图书加入到k的后面
            for (int k = j + 1; k < n; ++k) {
   
                memcpy(m[u], w, sizeof w);
                int x, y;
                for (x = j + 1, y = i; x <= k; ++x, ++y) w[y] = m[u][x];
                for (x = i; x <= j; ++x, ++y) w[y] = m[u][x];
                if (dfs(u + 1, max_dep)) return true;
                memcpy(w, m[u], sizeof w);
            }
        }
    }
    return false;
}

void solve() {
   
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    for (int k = 0; k < 5; ++k) {
   
        if (dfs(0, k)) {
   
            cout << k << '\n';
            return;
        }
    }

    cout << "5 or more" << '\n';
}

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

    cin >> T;
    while (T--) solve();

    return 0;
}

回转游戏

在这里插入图片描述

优化搜索顺序: 在执行完 $A$ 操作之后不能进行 $F$ 操作, 类似的在所有方向上执行完操作之后不能执行相反方向的操作, 因为相当于没操作并且增加了递归的深度
启发式剪枝: 因为要求中心 $8$ 个数字相同, 统计 $8$ 个数字中出现次数最多的数字, 并且每次操作最多改变 $8$ 个方格中的一个数字, 估价函数就是最小操作次数 $f = 8 - c n t$ , $c n t$ 是出现次数最多的数字出现的次数
假设当前情况操作次数 $p$ , 如果有 $\ge res$ , 剪枝

在这里插入图片描述
对所有操作进行标号, 同时记录每个操作需要移动下标

#include <bits/stdc++.h>

using namespace std;

const int N = 8, M = 24;
const int mp[8][7] = {
   
        {
   0, 2, 6, 11, 15, 20, 22},
        {
   1, 3, 8, 12, 17, 21, 23},
        {
   10, 9, 8, 7, 6, 5, 4},
        {
   19, 18, 17, 16, 15, 14, 13},
        {
   23, 21, 17, 12, 8, 3, 1},
        {
   22, 20, 15, 11, 6, 2, 0},
        {
   13, 14, 15, 16, 17, 18, 19},
        {
   4, 5, 6, 7, 8, 9, 10}
};
map<int, int> rev = {
   {
   0, 5},
                   {
   1, 4},
                   {
   2, 7},
                   {
   3, 6},
                   {
   4, 1},
                   {
   5, 0},
                   {
   6, 3},
                   {
   7, 2}};
int center[8] = {
   6, 7, 8, 11, 12, 15, 16, 17};

int g[M];
int ans[N * M];

bool check() {
   
    int val = g[center[0]];
    for (int i : center) {
   
        if (g[i] != val) return false;
    }
    return true;
}

void move(int i) {
   
    int val = g[mp[i][0]];
    for (int j = 0; j < 6; ++j) {
   
        g[mp[i][j]] = g[mp[i][j + 1]];
    }
    g[mp[i][6]] = val;
}

int est() {
   
    int cnt[4] = {
   0};
    for (int i : center) {
   
        cnt[g[i]]++;
    }
    int max_cnt = 0;
    for (int val : cnt) max_cnt = max(max_cnt, val);
    return max(0, 8 - max_cnt);
}

bool dfs(int u, int max_dep, int last) {
   
    if (u > max_dep) return false;
    if (u + est() > max_dep) return false;
    if (check()) return true;

    for (int i = 0; i < 8; ++i) {
   
        if (rev[i] != last) {
   
            move(i);
            ans[u] = i;
            if (dfs(u + 1, max_dep, i)) return true;
            move(rev[i]);
        }
    }

    return false;
}

void solve() {
   
    if (check()) {
   
        cout << "No moves needed" << '\n';
        cout << g[center[0]] << '\n';
        return;
    }

    for (int dep = 1; ; ++dep) {
   
        if (dfs(0, dep, -1)) {
   
            for (int i = 0; i < dep; ++i) cout << char(ans[i] + 'A');
            cout << '\n';
            cout << g[center[0]] << '\n';
            break;
        }
    }
}

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

    while (cin >> g[0], g[0]) {
   
        for (int i = 1; i < M; ++i) cin >> g[i];
        solve();
    }

    return 0;
}

基础搜索算法

目录

F l o o d − F i l l Flood-Fill Flood−Fill方法

池塘计数

城堡问题

山峰和山谷

最短路模型

迷宫问题

武士风度的牛

抓住那头牛

多源 B F S BFS BFS

矩阵距离

最小步数模型

魔板

双端队列搜索 / 双向 B F S BFS BFS搜索

电路维修(双端队列广搜)

字符串变换(双向广搜)

双向广度搜索写法

A ∗ A* A∗算法(优化BFS)

第 K K K短路

八数码问题

DFS搜索

迷宫问题

红与黑

经典问题之马走日

单词接龙

分为互质组

DFS剪枝优化

小猫爬山

数独

木棒

生日蛋糕**

双向DFS

送礼物

迭代加深搜索

加成序列

I D A ∗ IDA* IDA∗算法

排书问题

回转游戏

$Fl oo d - F i ll$ 方法

多源 $BFS$

双端队列搜索 / 双向 $BFS$ 搜索

$A *$ 算法(优化BFS)

第 $K$ 短路

$I D A *$ 算法