题目描述

https://www.acwing.com/problem/content/1208/

简单聊聊

这题打破了我写最长算法的长度(150行),在此记录下。第一次做这种复杂度远超我想象的题，本来以为就是个dfs，没想到要用这么多算法，也算是对基础课的巩固吧。本来是不想写题解的，但是看到题解区貌似没有题解给y总代码上些注释，这对像我这样的视频党很不友好呀，所以就根据我自己的理解写了些注释，方便后人更快读懂y总的奇妙思路吧。具体的图什么帮助理解是真的不想画了，这题想了好久= =，以后有时间再说吧(下次一定)，其实多看几遍视频也基本可以理解的。代码中如果有地方注释不太得当，请在评论区留言。

算法1

(dfs + 剪枝 + 并查集 + 字符串哈希) $O(鬼知道)$

C++ 代码

/*
    dfs + 剪枝 + 并查集 + 字符串哈希
    从左上角开始搜索，需要保证考虑两件事 1. 搜索的是一个连通块，且搜索以后剩下的方块也是一个连通块
                                         2. 搜索的连通块不一定是一条欧拉通路
    所以需要在套一层循环，将每次扩展得到的点加入一个点集中，每次从每个已经搜索的点
    扩展分支(看到评论好像叫做锯齿形搜索，不过我更喜欢叫分支dfs), 并且对于每个点可扩展的
    点，需要从大到小排序，因为是从上往下搜的，从大到小，搜索路径更短，更方便剪枝。另外
    ，这题的剪枝其实就是对每次扩展以后的点的一个连通块进行一个字符串哈希，判断是否之前
    出现过这种情况，这样可以少遍历一些
    具体函数实现看下面注释
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#define x first
#define y second

using namespace std;

const int N = 10, INF = 1e8, P = 131;

typedef unsigned long long ULL;
typedef pair<int, int> PII;

int n, m;
int g[N][N];
bool st[N][N];   // st用于判断剩余方块是否是一个连通块
int sum, ans = INF;  // sum是所有数的总和，ans是答案
PII cands[N * N];  // 搜索路径上已经选择的点
int p[N * N];   // 并查集判断连通块
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 偏移量

unordered_set<ULL> hash_table;

int find(int x)  // 并查集模板
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool check_connet(int k)  // 判断剩余方块是否是一个连通块
{
    for(int i = 0; i < n * m; i ++) p[i] = i; // 初始化并查集

    int cnt = n * m - k;  // 剩余的点的数量

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(!st[i][j])
            {
                for(int u = 0; u < 4; u ++)
                {
                    int a = i + dx[u], b = j + dy[u];
                    // 如果越界或者已经搜过则跳过
                    if(a < 0 || a >= n || b < 0 || b >= m) continue;
                    if(st[a][b]) continue;
                    // 得到对应方格的编号对应的并查集中的父节点
                    int p1 = find(i * m + j), p2 = find(a * m + b);
                    if(p1 != p2) // 合并
                    {
                        p[p1] = p2;
                        cnt --;
                    }
                }
            }
    if(cnt != 1) return false;
    return true;
}

bool check_exists(int k) // 这是剪枝的关键，判断扩展后的结果在之前是否出现过
{
    PII bk[N * N];
    for(int i = 0; i < k; i ++) bk[i] = cands[i];

    sort(bk, bk + k); // 这里不排序就会tle， 不知道为啥，求评论区大佬解惑？

    //严格来说，这并不是字符串哈希，只是运用那种思想来对每种情况进行区分而已
    ULL x = 0;
    for(int i = 0; i < k; i ++)
    {
        x = x * P + bk[i].x + 1;
        x = x * P + bk[i].y + 1;
    }
    if(hash_table.count(x)) return true; // 如果之前已经出现过,则返回真

    hash_table.insert(x);
    return false;
}

void dfs(int s, int k) // s 表示当前搜索数的总和，k 表示当前搜索路径的点的数量
{
    if(s == sum / 2)
    {
        // 如果剩下的方块是一个连通块，则更新答案
        if(check_connet(k)) ans = min(ans, k);
        return;
    }

    vector<PII> points; // 存储可扩展的点

    for(int i = 0; i < k; i ++)  // 对搜索路径上的每个点进行扩展
    {
        int x = cands[i].x, y = cands[i].y;
        for(int j = 0; j < 4; j ++)
        {
            int a = x + dx[j], b = y + dy[j];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(st[a][b]) continue;

            cands[k] = {a, b};  // 将该点加入点集，才可以判断有这个点的连通块的情况
            // 如果新扩展的点使得数量比答案要大或者前面已经有过这种扩展方案，则不用扩展该点
            if(k + 1 < ans && !check_exists(k + 1))
                points.push_back({a, b});
        }
    }

    // 对可扩展的点要从大到小排序
    sort(points.begin(), points.end());
    reverse(points.begin(), points.end());

    for(int i = 0; i < points.size(); i ++)
        if(!i || points[i] != points[i - 1]) // 如果是第一个点或者该点与上一个点不同
        {
            cands[k] = points[i];
            int x = points[i].x, y = points[i].y;
            st[x][y] = true;
            dfs(s + g[x][y], k + 1);  // 往下扩展
            st[x][y] = false;   // 恢复现场
        }
}

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

    if(sum % 2 == 0){  // 偶数才可以平分
        st[0][0] = true;  // 从左上角开始搜
        cands[0] = {0, 0};
        dfs(g[0][0], 1);
    }

    if(ans == INF) ans = 0;
    cout << ans << endl;
    return 0;
}