AcWing 182. 破坏正方形 题解

题目分析

本题给定一个由火柴棍构成的(n×n)（(n)不大于(5)）的完整或不完整网格，每根火柴棍有唯一编号。需要找出至少再去掉多少根火柴棒，能使网格内不再包含任何尺寸的正方形。

解题思路

本题采用舞蹈链（DLX）算法结合状态搜索的方法。将每个正方形看作一个需要被覆盖的列，每根火柴棍看作一个行，构建一个(0 - 1)矩阵。若某根火柴棍是某个正方形的边，则矩阵中对应位置为(1)，否则为(0)。通过舞蹈链算法搜索矩阵，找到能使所有正方形都被破坏（即每列恰好有一个(1)被选取，代表去掉对应的火柴棍）的最少行数（即最少去掉的火柴棍数量）。

代码逐段分析

1. 头文件和全局变量定义

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 3600;

int n, m;
int l[N], r[N], u[N], d[N], col[N], row[N], s[N], idx;
vector<int> square[60];
bool st[60];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于算法相关功能，vector用于动态数组。
• 定义常量(N)，表示可能的最大节点数。
• 变量(n)表示网格的边长，(m)表示正方形的数量。
• l、r、u、d数组分别表示双向链表的左、右、上、下指针；col数组记录每个节点所在的列；row数组记录每个节点所在的行；s数组记录每列中(1)的个数；idx用于节点编号。
• square数组用于存储每个正方形所包含的火柴棍编号。

• st数组用于标记火柴棍是否已经被去掉。

• 初始化函数

void init()
{
    for (int i = 0; i <= m; i ++ )
    {
        l[i] = i - 1, r[i] = i + 1;
        col[i] = u[i] = d[i] = i;
        s[i] = 0;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}

初始化双向链表，构建列头节点的双向循环链表，设置每列头节点的上下指针指向自身，左右指针构成循环，同时初始化每列的元素计数为(0)。设置头节点的左右指针构成循环，并初始化节点编号idx从(m + 1)开始。

1. 添加节点函数

void add(int& hh, int& tt, int x, int y)
{
    row[idx] = x, col[idx] = y, s[y] ++ ;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx ++ ;
}

向双向链表中添加一个节点。记录节点所在的行x和列y，增加列y中(1)的计数。在垂直方向上，将新节点插入到列头节点和原列中下方节点之间；在水平方向上，将新节点插入到当前行已有节点的末尾。最后更新行尾指针tt并递增节点编号idx。

1. 启发式函数

int h()
{
    int res = 0;
    memset(st, 0, sizeof st);
    for (int i = r[0]; i; i = r[i])
    {
        if (st[i]) continue;
        st[i] = true;
        res ++ ;
        for (int j = d[i]; j != i; j = d[j])
            for (int k = r[j]; k != j; k = r[k])
                st[col[k]] = true;
    }
    return res;
}

启发式函数，用于估算当前状态下还需要选取的最少行数。遍历每一列，若该列未被标记，标记该列并增加计数，同时标记该列中所有节点所在的列，最后返回计数结果。

1. 删除列函数

void remove(int p)
{
    for (int i = d[p]; i != p; i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}

删除指定列p及其相关的节点。遍历该列中的每个节点，将其从水平链表中移除。

1. 恢复列函数

void resume(int p)
{
    for (int i = u[p]; i != p; i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}

恢复之前删除的列p及其相关节点。遍历该列中的每个节点，将其重新插入到水平链表中。

1. 深度优先搜索函数

bool dfs(int k, int depth)
{
    if (k + h() > depth) return false;
    if (!r[0]) return true;
    int p = r[0];
    for (int i = r[0]; i; i = r[i])
        if (s[p] > s[i])
            p = i;

    for (int i = d[p]; i != p; i = d[i])
    {
        remove(i);
        for (int j = r[i]; j != i; j = r[j]) remove(j);
        if (dfs(k + 1, depth)) return true;
        for (int j = l[i]; j != i; j = l[j]) resume(j);
        resume(i);
    }
    return false;
}

深度优先搜索函数，用于寻找满足条件的最少火柴棍数量。
- 如果当前已选取的行数加上启发式函数估算的最少还需选取的行数大于给定的深度depth，则返回false，表示该搜索路径不可行。
- 如果头节点的右指针指向自身（即(r[0] == 0)），说明所有列都已被覆盖，返回true。
- 选择当前列中元素个数最少的列p，遍历该列中的每个节点i，删除该节点及其所在行的所有节点，递归调用dfs继续搜索，如果找到解则返回true。若递归搜索失败，则恢复之前删除的节点。
- 如果所有节点都遍历完仍未找到解，则返回false。

1. 主函数

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        memset(st, 0, sizeof st);
        int cnt;
        scanf("%d", &cnt);
        while (cnt -- )
        {
            int x;
            scanf("%d", &x);
            st[x] = true;
        }

        m = 0;
        for (int len = 1; len <= n; len ++ )
            for (int a = 1; a + len - 1 <= n; a ++ )
                for (int b = 1; b + len - 1 <= n; b ++ )
                {
                    auto& sq = square[ ++ m];
                    sq.clear();
                    int d = n * 2 + 1;
                    for (int i = 0; i < len; i ++ )
                    {
                        sq.push_back((a - 1) * d + b + i);
                        sq.push_back((a - 1) * d + b + i + d * len);
                        sq.push_back((a - 1) * d + b + n + d * i);
                        sq.push_back((a - 1) * d + b + n + d * i + len);
                    }

                    for (auto x: sq)
                        if (st[x])
                        {
                            m -- ;
                            break;
                        }
                }

        init();
        for (int i = 1; i <= n * (n + 1) * 2; i ++ )
            if (!st[i])
            {
                int hh = idx, tt = idx;
                for (int j = 1; j <= m; j ++ )
                {
                    auto& sq = square[j];
                    if (find(sq.begin(), sq.end(), i) != sq.end())
                        add(hh, tt, i, j);
                }
            }

        int depth = 0;
        while (!dfs(0, depth)) depth ++ ;
        printf("%d\n", depth);
    }

    return 0;
}

• 读取测试用例的数量T，对于每个测试用例：
  • 读取网格的边长n，已去掉的火柴棍数量cnt，以及已去掉的火柴棍编号，并标记在st数组中。
  • 计算并存储所有可能的正方形及其包含的火柴棍编号，同时排除已经去掉的火柴棍所在的正方形。
  • 初始化舞蹈链。
  • 遍历未去掉的火柴棍，将其与包含它的正方形建立双向链表连接。
  • 从深度0开始，不断增加深度，调用dfs函数进行搜索，直到找到满足条件的解，输出最少需要去掉的火柴棍数量。

时间复杂度分析

在最坏情况下，舞蹈链算法的时间复杂度是指数级的。但由于使用了启发式函数进行剪枝，实际运行时能减少搜索空间，平均时间复杂度会有所降低。

空间复杂度分析

主要空间消耗在于存储双向链表的各种数组、记录正方形的square数组以及标记数组st等，空间复杂度为(O(N))，其中(N)是节点和相关数据结构的最大数量。