• 【算法1-7】搜索 - 题单 - 洛谷 | 计算机科学教育新生态
• CMの搜索 - 题单 - 洛谷 | 计算机科学教育新生态

题单 1 ：

P1219 八皇后 Checker Challenge

DFS

void solve() {
    int n;cin >> n;
    int sum = 0;
    array<int, 15> ans = {};
    vector<array<int, 30>> check(3);
    auto dfs = [&](auto self, int x)->void {
        if (x > n) {
            sum++;
            if (sum > 3)return;
            for (int i = 1;i <= n;i++)cout << ans[i] << " \n"[i == n];return;
        }
        for (int i = 1;i <= n;i++) {
            if (!check[0][i] && !check[1][x + i] && !check[2][x + n - i]) {
                ans[x] = i;
                check[0][i] = 1;
                check[1][x + i] = 1;
                check[2][x + n - i] = 1;
                self(self, x + 1);
                check[0][i] = 0;
                check[1][x + i] = 0;
                check[2][x + n - i] = 0;
            }
        }
        };
    dfs(dfs, 1);
    cout << sum << '\n';
}

P2392 kkksc03考前临时抱佛脚

DFS/DP

void solve() {
    int l[4] = {};
    for (int i = 0;i < 4;i++) {
        cin >> l[i];
    }
    vector<vector<int>> a(4);
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < l[i];j++) {
            int x;cin >> x;a[i].push_back(x);
        }
    }
    int sum = 0;
    for (int i = 0;i < 4;i++) {
        int mi = 1e9, left = 0, right = 0;
        auto dfs = [&](auto self, int x) ->void {
            if (x >= a[i].size()) {
                mi = min(max(left, right), mi);return;
            }
            left += a[i][x];
            self(self, x + 1);
            left -= a[i][x];
            right += a[i][x];
            self(self, x + 1);
            right -= a[i][x];
            };
        dfs(dfs, 0);
        sum += mi;
    }
    cout << sum << '\n';
}

P1443 马的遍历

BFS

int dx[] = {1, -1, 1, -1, 2, 2, -2, -2};
int dy[] = {2, 2, -2, -2, -1, 1, -1, 1};
void solve() {
    int n, m, x, y;cin >> n >> m >> x >> y;
    vector<vector<int>> dis(n + 1, vector<int>(m + 1, -1));
    queue<pair<int, int>> q;
    q.push({x,y});
    dis[x][y] = 0;
    while (q.size()) {
        auto [a, b] = q.front();q.pop();
        for (int i = 0;i < 8;i++) {
            int cx = a + dx[i], cy = b + dy[i];
            if (cx<1 || cy<1 || cx>n || cy>m)continue;
            if (dis[cx][cy] != -1)continue;
            dis[cx][cy] = dis[a][b] + 1;
            q.push({cx,cy});
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << left << setw(4) << dis[i][j] << " \n"[j == m];
        }
    }
}

P1135 奇怪的电梯

DFS/BFS

void solve() {
    int n, a, b;cin >> n >> a >> b;vector<int> p(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> p[i];
    }
    int ans = 1e9;
    vector<bool> ok(n + 1);
    auto dfs = [&](auto self, int x, int cnt) -> void {
        if (cnt >= ans)return;
        if (x == b) {
            ans = min(ans, cnt);
            return;
        }
        if (x + p[x] <= n && !ok[x + p[x]]) {
            ok[x] = 1;
            self(self, x + p[x], cnt + 1);
            ok[x] = 0;
        }
        if (x - p[x] >= 1 && !ok[x - p[x]]) {
            ok[x] = 1;
            self(self, x - p[x], cnt + 1);
            ok[x] = 0;
        }
        };
    dfs(dfs, a, 0);
    if (ans == 1e9)ans = -1;
    cout << ans << '\n';
}

void solve() {
    int n, a, b;cin >> n >> a >> b;
    vector<ll> p(n + 1), dis(n + 1, -1);
    for (int i = 1;i <= n;i++)cin >> p[i];

    queue<int> q;q.push(a);dis[a] = 0;
    while (q.size()) {
        auto x = q.front();q.pop();
        if (!p[x])continue;
        if (x - p[x] >= 1) {
            if (dis[x - p[x]] != -1)goto next;
            dis[x - p[x]] = dis[x] + 1;q.push(x - p[x]);
        }
        next:
        if (x + p[x] <= n) {
            if (dis[x + p[x]] != -1)continue;
            dis[x + p[x]] = dis[x] + 1;q.push(x + p[x]);
        }
    }
    cout << dis[b] << ' ';
}

P2895 Meteor Shower S

BFS

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int p[310][310], dis[310][310];
void solve() {
    int m;cin >> m;
    for (int i = 0;i < 310;i++) {
        for (int j = 0;j < 310;j++) {
            p[i][j] = 1010;
        }
    }
    for (int i = 1;i <= m;i++) {
        int x, y, t;cin >> x >> y >> t;
        p[x][y] = min(t, p[x][y]);
        p[x + 1][y] = min(t, p[x + 1][y]);
        p[x][y + 1] = min(t, p[x][y + 1]);
        if (x - 1 >= 0)
            p[x - 1][y] = min(t, p[x - 1][y]);
        if (y - 1 >= 0)
            p[x][y - 1] = min(t, p[x][y - 1]);
    }
    queue <pair<int, int>> q;q.push({0,0});
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0)continue;
            if (dis[a][b])continue;
            if (dis[x][y] + 1 >= p[a][b])continue;//若这个地方已经不能再进去了
            dis[a][b] = dis[x][y] + 1;
            q.push({a,b});
            if (p[a][b] == 1010) {
                cout << dis[a][b] << "\n";return;
            }
        }
    }
    cout << "-1\n";
}

P1036 选数

DFS-有点迷糊的搜索

void solve() {
    int n, k;cin >> n >> k;vector<int>a(n);
    for (int i = 0;i < n;i++)cin >> a[i];
    int ans = 0;
    auto dfs = [&](auto self, int x, int sum, int sx)->void {
        if (x == k) {
            if (isPrime(sum))ans++;return;
        }
        for (int i = sx;i < n;i++)self(self, x + 1, sum + a[i], i + 1);
        };
    dfs(dfs, 0, 0, 0);
    cout << ans << '\n';
}

P2036 PERKET

void solve() {
    int n;cin >> n;vector<int> a(n + 1), b(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i] >> b[i];
    int ans = 1e9;
    /*------------1----------------*/
    auto dfs = [&](auto self, int x)->void {
        if (x > n) {
            int s = 1, k = 0;
            for (int i = 1;i <= n;i++) {
                if (vis[i] == 1) {
                    s *= a[i];k += b[i];ans = min(ans, abs(s - k));//这里可以保证全不选不能进入
                }
            }
            return;
        }
        vis[x] = 1;//选
        self(self, x + 1);
        vis[x] = 0;
        vis[x] = 2;//不选
        self(self, x + 1);
        vis[x] = 0;
        };
    dfs(dfs, 0);
    /*------------2----------------*/
    auto dfs = [&](auto self, int x, int s, int k)->void {
        if (x > n) {
            if (s == 1 && k == 0)return;//必须添加至少一种配料，不能全不选
            ans = min(ans, abs(s - k));return;
        }
        self(self, x + 1, s * a[x], k + b[x]);//选
        self(self, x + 1, s, k);//不选
        };
    dfs(dfs, 1, 1, 0);
    cout << ans << '\n';
}

P1433 吃奶酪

DFS+状态压缩

状压DP

(看不懂，学完 DP 再来)

void solve() {
    int n;cin >> n;
    vector<array<double, 33000>> f(16);
    vector<int> vis(16);
    vector<pair<double, double>> p(16);
    auto dis = [&](int x, int y) {
        return sqrt((p[x].first - p[y].first) * (p[x].first - p[y].first) + (p[x].second - p[y].second) * (p[x].second - p[y].second));
        };
    for (int i = 1;i <= n;i++)cin >> p[i].first >> p[i].second;
    double ans = DBL_MAX;
    auto dfs = [&](auto self, int step, int x, int mark, double s) ->void {
        if (s > ans)return;
        if (step == n) {
            ans = min(ans, s);return;
        }
        for (int i = 1;i <= n;i++) {
            if (vis[i])continue;
            int m = mark + (1 << (i - 1));
            if (f[i][m] != 0 && f[i][m] <= s + dis(i, x))continue;
            vis[i] = 1;
            f[i][m] = s + dis(i, x);
            self(self, step + 1, i, m, f[i][m]);
            vis[i] = 0;
        }
        };
    dfs(dfs, 0, 0, 0, 0);
    cout << fixed << setprecision(2) << ans << '\n';
}

P1605 迷宫

DFS

void solve() {
    int n, m, t;cin >> n >> m >> t;
    vector<vector<int>> vis(n + 1, vector<int>(m + 1));
    int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;
    for (int i = 1;i <= t;i++) {
        int x, y;cin >> x >> y;vis[x][y] = 1;
    }
    int ans = 0;
    auto dfs = [&](auto self, int x, int y)->void {
        if (x == x2 && y == y2) {
            ans++;return;
        }
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m)continue;
            if (vis[a][b])continue;
            vis[a][b] = 1;
            self(self, a, b);
            vis[a][b] = 0;
        }
        };
    vis[x1][y1] = 1;
    dfs(dfs, x1, y1);
    cout << ans << '\n';
}

P1101 单词方阵

int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
int vis[110][110];
void solve() {
    int n;string s[n];cin >> n;
    for (int i = 0;i < n;i++)cin >> s[i];
    string tar = "yizhong";
    auto find = [&](int x, int y) {
        for (int i = 0;i < 8;i++) {
            int step = 0;
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= n)continue;
            while (step < 6 && s[a][b] == tar[step + 1]) {
                a += dx[i]; b += dy[i];step++;
            }
            if (step == 6) {
                for (int j = 0;j < n;j++) {
                    for (int k = 0;k < n;k++) {
                        if (j == x && k == y) {
                            for (int p = 0;p < 7;p++) {
                                vis[j][k] = 1;j += dx[i], k += dy[i];
                            }
                            return;
                        }
                    }
                }
            }
        }
        };
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (s[i][j] == 'y') {
                find(i, j);
            }
        }
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (vis[i][j]) {
                cout << s[i][j];
            } else {
                cout << '*';
            }
        }
        cout << '\n';
    }
}

P2404 自然数的拆分问题

DFS

int n;vector<int> a(10, 1);
void dfs(int m, int x) {
    for (int i = a[x - 1];i <= m;i++) {
        a[x] = i;m -= i;
        if (!m) {
            if (x == 1)return;
            for (int i = 1;i <= x - 1;i++) {
                cout << a[i] << "+";
            }
            cout << a[x] << '\n';
        } else dfs(m, x + 1);
        m += i;
    }
}
void solve() {
    cin >> n;
    dfs(n, 1);
}

P1596 Lake Counting S

DFS

string s[110];
int n, m, vis[110][110];
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
void dfs(int x, int y) {
    for (int i = 0;i < 8;i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a<1 || b<1 || a>n || b>m)continue;
        if (vis[a][b])continue;
        if (s[a][b] == '.')continue;
        vis[a][b] = 1;
        dfs(a, b);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        string ss;cin >> ss;ss = ' ' + ss;s[i] = ss;
    }
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == 'W' && !vis[i][j]) {
                vis[i][j] = 1;
                dfs(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << '\n';
}

P1162 填涂颜色

DFS/BFS

int n, s[35][35], vis[35][35], op[35][35];bool ok;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void dfs(int x, int y) {
    for (int i = 0;i < 4;i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a<1 || b<1 || a>n || b>n) {
            ok = false;continue;
        }
        if (s[a][b])continue;
        if (vis[a][b])continue;
        vis[a][b] = 1;
        op[a][b] = 1;
        dfs(a, b);
    }
}
void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (!s[i][j] && !vis[i][j]) {
                ok = true;
                for (int k = 1;k <= n;k++) {
                    for (int p = 1;p <= n;p++) {
                        op[k][p] = 0;
                    }
                }
                vis[i][j] = 1;op[i][j] = 1;
                dfs(i, j);
                if (ok) {
                    for (int k = 1;k <= n;k++) {
                        for (int p = 1;p <= n;p++) {
                            if (op[k][p]) {
                                s[k][p] = 2;
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cout << s[i][j] << " \n"[j == n];
        }
    }
}

BFS 法一：由于题目说的是只有一个环，将外圈看一遍即可。

void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s[i][j];
        }
    }
    auto bfs = [&](int i, int j) ->void {
        if (s[i][j])return;
        queue<pair<int, int>>q;
        q.push({i,j});vis[i][j] = 1;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 4;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>n)continue;
                if (vis[a][b])continue;
                if (s[a][b])continue;
                vis[a][b] = 1;
                q.push({a,b});
            }
        }
        };

    for (int i = 1;i <= n;i++) {
        bfs(1, i);bfs(i, 1);bfs(n, i);bfs(i, n);
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (!s[i][j] && !vis[i][j]) {
                s[i][j] = 2;
            }
            cout << s[i][j] << " \n"[j == n];
        }
    }
}

BFS 法二：这里的思路和法一相同，但是这里更为简洁的是自行构建了一个外圈，也是扫描一遍外圈即可，这样简化了代码。

void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s[i][j];
        }
    }
    queue<pair<int, int>>q;
    q.push({1,1});vis[1][1] = 1;
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<0 || b<0 || a>n + 1 || b>n + 1)continue;
            if (vis[a][b])continue;
            if (s[a][b])continue;
            vis[a][b] = 1;
            q.push({a,b});
        }
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (!s[i][j] && !vis[i][j]) {
                s[i][j] = 2;
            }
            cout << s[i][j] << " \n"[j == n];
        }
    }
}

P1032 字串变换

DFS /字符串(KMP $\dots$)

正解->双向BFS

HACK：

abaaaba abcdaba
a b
b d
d e
e f
f g
g c

a aaaaa
a a112233445566778899
778899 a
112233 a
445 a
566 a
55 a

DFS 做的话，这两个数据都会引起字符串的爆炸一定会 T，都是经过特判才过的。

void solve() {
    int vis[20] = {};
    string aa, bb, a, b, x, y;cin >> aa >> bb;
    vector<string> op1, op2;
    if (aa.size() == bb.size()) {
        for (int i = 0;i < aa.size();i++) {
            if (aa[i] != bb[i]) {
                a.push_back(aa[i]);b.push_back(bb[i]);
            }
        }
    } else {
        a = aa;b = bb;
    }
    while (cin >> x >> y) {
        op1.push_back(x);
        op2.push_back(y);
    }
    int ans = 1e9;
    auto dfs = [&](auto self, int cnt)->void {
        if (cnt > 20) {
            cout << "NO ANSWER!" << '\n';exit(0);
        }
        if (a == b) {
            ans = min(ans, cnt);return;
        }
        for (int i = 0;i < a.size();i++) {
            for (int j = i;j < a.size();j++) {
                for (int k = 0;k < op1.size();k++) {
                    if (a.substr(i, j - i + 1) == op1[k] && !vis[k]) {
                        if (j - i + 1 == a.size()) {
                            vis[k] = 1;
                        }
                        string ss(a.begin() + i, a.begin() + j + 1);
                        a.replace(a.begin() + i, a.begin() + j + 1, op2[k]);
                        self(self, cnt + 1);
                        a.replace(a.begin() + i, a.begin() + j + 1 + op2.size() - op1.size(), ss);
                    }
                }
            }
        }
        };
    dfs(dfs, 0);
    if (ans > 10) {
        cout << "NO ANSWER!" << '\n';return;
    }
    cout << ans << '\n';
}

正解：双向BFS：

可以将 BFS 中简化为一段。

void solve() {
    string a, b, s1, s2;cin >> a >> b;
    vector<string> op1, op2;
    while (cin >> s1 >> s2) {
        op1.push_back(s1);
        op2.push_back(s2);
    }
    queue<string> qa, qb;unordered_map <string, int> ma, mb;
    qa.push(a), qb.push(b);ma[a] = 0, mb[b] = 0;
    int ans;
    auto bfs = [&](bool x)->int {
        if (!x) {
            int m = qa.size();
            while (m--) {
                auto s = qa.front();qa.pop();
                for (int i = 0;i < op1.size();i++) {
                    for (int j = 0;j + op1[i].size() - 1 < s.size();j++) {
                        if (s.substr(j, op1[i].size()) == op1[i]) {
                            string ss = s.substr(0, j) + op2[i] + s.substr(j + op1[i].size());
                            if (ma.count(ss))continue;
                            if (mb.count(ss))return ma[s] + mb[ss] + 1;
                            ma[ss] = ma[s] + 1;
                            qa.push(ss);
                        }
                    }
                }
            }
        } else {
            int m = qb.size();
            while (m--) {
                auto s = qb.front();qb.pop();
                for (int i = 0;i < op2.size();i++) {
                    for (int j = 0;j + op2[i].size() - 1 < s.size();j++) {
                        if (s.substr(j, op2[i].size()) == op2[i]) {
                            string ss = s.substr(0, j) + op1[i] + s.substr(j + op2[i].size());
                            if (mb.count(ss))continue;
                            if (ma.count(ss))return mb[s] + ma[ss] + 1;
                            mb[ss] = mb[s] + 1;
                            qb.push(ss);
                        }
                    }
                }
            }
        }
        return 11;
        };
    for (int i = 1;i <= 10;i++) {
        if (qa.size() <= qb.size()) {
            ans = bfs(0);
        } else {
            ans = bfs(1);
        }
        if (ans <= 10) {
            cout << ans << '\n';return;
        }
    }
    cout << "NO ANSWER!" << '\n';
}

P 1825 Corn Maze S

BFS 但是毒瘤

char s[310][310];
int dis[310][310];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    int sx, sy, ex, ey;
    map<char, vector<pair<int, int>>>mp;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == '@') sx = i, sy = j;
            if (s[i][j] == '=') ex = i, ey = j;
            if (isupper(s[i][j])) {
                mp[s[i][j]].push_back({i,j});
            }
            dis[i][j] = -1;
        }
    }
    queue<pair<int, int>>q;
    q.push({sx,sy});dis[sx][sy] = 0;
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        if (x == ex && y == ey) {
            cout << dis[x][y] << '\n';return;
        }
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m || s[a][b] == '#')continue;
            if (dis[a][b] == -1 || isupper(s[a][b])) {
                if (isupper(s[a][b])) {
                    auto find = [&]()->pair<int, int> {
                        for (auto [j, k] : mp[s[a][b]]) {
                            if (j != a || k != b) {
                                return {j,k};
                            }
                        }
                        };
                    auto [j, k] = find();
                    if (dis[j][k] == -1) {
                        dis[j][k] = dis[x][y] + 1;
                    }
                    q.push({j,k});
                } else { // if (dis[a][b] == -1)
                    dis[a][b] = dis[x][y] + 1;
                    q.push({a,b});
                }
            }
        }
    }
}

题单 2：

P1157 组合的输出

DFS

void solve() {
    int n, r;cin >> n >> r;
    vector<int> a(r + 1);
    auto dfs = [&](auto self, int x)->void {
        if (x > r) {
            for (int i = 1;i <= r;i++) {
                cout << setw(3) << a[i];
            }
            cout << '\n';
            return;
        }
        for (int i = a[x - 1] + 1;i <= n;i++) {
            a[x] = i;
            self(self, x + 1);
        }
        };
    dfs(dfs, 1);
}

P1706 全排列问题

DFS

void solve() {
    int n;cin >> n;vector<int>a(n + 1);
    for (int i = 1;i <= n;i++)a[i] = i, cout << setw(5) << a[i]; cout << '\n';
    while (next_permutation(a.begin() + 1, a.end())) {
        for (int i = 1;i <= n;i++)cout << setw(5) << a[i]; cout << '\n';
    }
}

void solve() {
    int n;cin >> n;vector<int>a(n + 1), vis(n + 1);
    auto dfs = [&](auto self, int x) ->void {
        if (x > n) {
            for (int i = 1;i <= n;i++)cout << setw(5) << a[i];cout << '\n';return;
        }
        for (int i = 1;i <= n;i++) {
            if (!vis[i]) {
                a[x] = i;
                vis[i] = 1;
                self(self, x + 1);
                vis[i] = 0;
            }
        }
        };
    dfs(dfs, 1);
}

P1256 显示图像

BFS

int dis[200][200], vis[200][200];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    string s[n + 1];
    for (int i = 1;i <= n;i++) {
        string ss;cin >> ss;ss = ' ' + ss;s[i] = ss;
    }
    queue<pair<int, int>> q;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '1') {
                vis[i][j] = 1;
                q.push({i,j});
            }
        }
    }
    while (q.size()) {
        auto [a, b] = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int cx = a + dx[i], cy = b + dy[i];
            if (cx<1 || cy<1 || cx>n || cy>m || vis[cx][cy])continue;
            vis[cx][cy] = 1;
            dis[cx][cy] = dis[a][b] + 1;
            q.push({cx,cy});
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << dis[i][j] << " \n"[j == m];
        }
    }
}

P1683 入门

DFS/BFS

char s[25][25];
bool vis[25][25];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void solve() {
    int m, n;cin >> m >> n;
    int sx, sy;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == '@')sx = i, sy = j;
        }
    }
    queue<pair<int, int>> q;vis[sx][sy] = 1;q.push({sx,sy});
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m || s[a][b] == '#' || vis[a][b])continue;
            vis[a][b] = 1;
            q.push({a,b});
        }
    }
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        cnt += count(vis[i] + 1, vis[i] + 1 + m, 1);
    }
    cout << cnt << '\n';
}

P1454 圣诞夜的极光

DFS/BFS

char s[110][110];
int vis[110][110];
int dx[] = {1, -1, 0, 0,1,1,-1,-1,2,-2,0,0};
int dy[] = {0, 0, 1, -1,1,-1,1,-1,0,0,2,-2};
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
        }
    }
    auto bfs = [&](int sx, int sy) {
        queue<pair<int, int>> q;vis[sx][sy] = 1;q.push({sx,sy});
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 12;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m || vis[a][b] || s[a][b] == '-')continue;
                vis[a][b] = 1;
                q.push({a,b});
            }
        }
        };
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '#' && !vis[i][j]) {
                bfs(i, j);cnt++;
            }
        }
    }
    cout << cnt << '\n';
}

P2802 回家

BFS

要保证时间最短，有鼠标的点只可能走一次，而要尽可能不死，正常的点有可能走多次。

int s[15][15], dis[15][15];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    int sx, sy, ex, ey;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == 2)sx = i, sy = j;
            if (s[i][j] == 3)ex = i, ey = j;
        }
    }
    queue<array<int, 4>>q;q.push({sx,sy,0,6});
    while (q.size()) {
        auto [x, y, step, hp] = q.front();q.pop();
        if (x == ex && y == ey) {
            cout << step << '\n';exit(0);
        }
        if (hp <= 1)continue;
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>m || !s[a][b])continue;
            if (s[a][b] == 1 || s[a][b] == 3) {
                if (dis[a][b] < hp - 1) {
                    dis[a][b] = hp - 1;
                    q.push({a,b,step + 1,hp - 1});
                }
            }
            if (s[a][b] == 4) {
                if (!dis[a][b]) {
                    dis[a][b] = 1;
                    q.push({a,b,step + 1,6});
                }
            }
        }
    }
    cout << "-1\n";
}

P6566 观星

BFS

char s[1510][1510];
int vis[1510][1510];
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
        }
    }
    map<int, int> mp;
    int cntvis = 0;
    auto bfs = [&](int sx, int sy) {
        queue<pair<int, int>>q;q.push({sx,sy});vis[sx][sy] = 1;cntvis++;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 8;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m || vis[a][b] || s[a][b] == '.')continue;
                vis[a][b] = 1;cntvis++;
                q.push({a,b});
            }
        }
        };
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '*' && !vis[i][j]) {
                int cnt = cntvis;
                bfs(i, j);
                mp[cntvis - cnt]++;
            }
        }
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans = max(ans, x * y);
    }
    cout << mp.size() << " " << ans << '\n';
}

P1746 离开中山路

BFS/双向 BFS

从起点和终点同时出发，起点走的标为 1，终点走的标为 2，一旦遇到就是最短路径

char s[1010][1010];
int vis[1010][1010], dis[1010][1010], dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s[i][j];
        }
    }
    int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;
    queue<pair<int, int>>q;
    q.push({x1,y1});q.push({x2,y2});vis[x1][y1] = 1;vis[x2][y2] = 2;
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a<1 || b<1 || a>n || b>n || s[a][b] == '1')continue;
            if (vis[a][b] + vis[x][y] == 3) {
                cout << dis[a][b] + dis[x][y] + 1 << '\n';exit(0);
            }
            if (vis[a][b])continue;
            vis[a][b] = vis[x][y];
            dis[a][b] = dis[x][y] + 1;
            q.push({a,b});
        }
    }
}

P2080 增进感情

DFS

艰难的卡过去的 900ms

void solve() {
    int n, v;cin >> n >> v;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;
        a[i] = {x + y,x - y};
    }
    int ans = 1e9;
    auto dfs = [&](auto self, int x, int sum, int m)->void {
        if (sum >= v) {
            ans = min(ans, abs(m));
            if (!ans)return;
        }
        if (x >= n)return;
        self(self, x + 1, sum + a[x + 1].first, m + a[x + 1].second);
        self(self, x + 1, sum, m);
        };
    dfs(dfs, 0, 0, 0);
    if (ans == 1e9)ans = -1;
    cout << ans << '\n';
}

P5635 天下第一

记忆化搜索

int mod;short f[10010][10010];
int dfs(int x, int y) {
    if (f[x][y] == -1)return -1;
    if (f[x][y])return f[x][y];
    f[x][y] = -1;
    if (!x)return f[x][y] = 1;
    if (!y)return f[x][y] = 2;
    int num = (x + y) % mod;
    return f[x][y] = dfs(num, (num % mod + y) % mod);
}
void solve() {
    int x, y;cin >> x >> y;
    int ans = dfs(x, y);
    if (ans == -1)cout << "error\n";
    else cout << ans << '\n';
}

或者用奇怪的方法卡过去。

void solve() {
    int x, y;cin >> x >> y;
    int i = 1;
    while (x && y && i <= 10000) {
        x = (x + y) % mod;
        if (!x) {
            cout << "1\n";return;
        }
        y = (x + y) % mod;i++;
        if (!y) {
            cout << "2\n";return;
        }
    }
    cout << "error\n";
}

P1332 血色先锋队

BFS

int vis[510][510], dis[510][510], dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};
void solve() {
    int n, m;cin >> n >> m;
    int a, b;cin >> a >> b;
    vector<pair<int, int>> t(b + 1);
    queue<pair<int, int>>q;
    for (int i = 1;i <= a;i++) {
        int x, y;cin >> x >> y;q.push({x,y});vis[x][y] = 1;
    }
    while (q.size()) {
        auto [x, y] = q.front();q.pop();

        for (int i = 0;i < 4;i++) {
            int cx = x + dx[i], cy = y + dy[i];
            if (cx<1 || cx>n || cy<1 || cy>m || vis[cx][cy])continue;
            vis[cx][cy] = 1;
            dis[cx][cy] = dis[x][y] + 1;
            q.push({cx,cy});
        }
    }
    for (int i = 1;i <= b;i++) {
        int x, y;cin >> x >> y;cout << dis[x][y] << '\n';
    }
}

P1747 好奇怪的游戏

BFS

int dx[] = {1, -1, 1, -1, 2, 2, -2, -2,2,2,-2,-2};
int dy[] = {2, 2, -2, -2, -1, 1, -1, 1,2,-2,2,-2};
void solve() {
    int x1, y1;cin >> x1 >> y1;int x2, y2;cin >> x2 >> y2;

    auto bfs = [&](int n, int m) {
        int vis[50][50] = {}, dis[50][50] = {};
        queue<pair<int, int>>q;q.push({n,m});vis[n][m] = 1;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            if (x == 1 && y == 1) {
                cout << dis[x][y] << '\n';break;
            }
            for (int i = 0;i < 12;i++) {
                int cx = x + dx[i], cy = y + dy[i];
                if (cx < 1 || cx>45 || cy < 1 || cy>45 || vis[cx][cy])continue;
                vis[cx][cy] = 1;
                dis[cx][cy] = dis[x][y] + 1;
                q.push({cx,cy});
            }
        }
        };
    bfs(x1, y1);
    bfs(x2, y2);
}

P2919 Guarding the Farm S

BFS/DFS

这个题目比较特殊的地方在于要从大到小的寻找。可以使用堆

int s[710][710], vis[710][710];
array<int, 3> a[710 * 710];
int dx[] = {0,0,-1,1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
void solve() {
    int n, m;cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            a[++cnt][2] = s[i][j];
            a[cnt][0] = i, a[cnt][1] = j;
        }
    }
    sort(a + 1, a + 1 + cnt, [&](auto x, auto y) {
        return x[2] > y[2];
        });
    auto bfs = [&](int cx, int cy) {
        queue<pair<int, int>>q;q.push({cx,cy});vis[cx][cy] = 1;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 8;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a<1 || b<1 || a>n || b>m || vis[a][b])continue;
                if (s[a][b] > s[x][y]) continue;
                vis[a][b] = 1;q.push({a,b});
            }
        }
        };
    int ans = 0;
    for (int i = 1;i <= cnt;i++) {
        int x = a[i][0], y = a[i][1];
        if (vis[x][y])continue;
        bfs(x, y);ans++;
    }
    cout << ans << '\n';
}

P2385 Bronze Lilypad Pond B

BFS

int a[35][35], vis[35][35], dis[35][35];
void solve() {
    int n, m, m1, m2;cin >> n >> m >> m1 >> m2;
    int dx[] = {m1,-m1,m2,-m2,m1,-m1,m2,-m2};
    int dy[] = {m2,m2,m1,m1,-m2,-m2,-m1,-m1};
    int sx, sy, ex, ey;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
            if (a[i][j] == 3)sx = i, sy = j;
            if (a[i][j] == 4)ex = i, ey = j;
        }
    }
    queue<pair<int, int>>q;q.push({sx,sy});vis[sx][sy] = 1;
    while (q.size()) {
        auto [x, y] = q.front();q.pop();
        if (x == ex && y == ey) {
            cout << dis[x][y] << '\n';return;
        }
        for (int i = 0;i < 8;i++) {
            int cx = x + dx[i], cy = y + dy[i];
            if (cx<1 || cy<1 || cx>n || cy>m || vis[cx][cy] || a[cx][cy] == 0 || a[cx][cy] == 2)continue;
            vis[cx][cy] = 1;dis[cx][cy] = dis[x][y] + 1;
            q.push({cx,cy});
        }
    }
}

P1790 矩形分割

同类型的题目：

• P1817 棋盘染色
• P4537 矩形
  (待更 $\dots$)

后面几个题做起来就没什么意义了。