题解：P11047 [蓝桥杯 2024 省 Java B] LITS 游戏

· · 题解

前置知识：精确覆盖问题

精确覆盖问题简单来说就是，给定 n 行 m 列的 01 矩阵，选出若干行使得对于选出的行中，对于第 j \in [1, m] 列有且仅有某一行的第 j 列为 1 。

舞蹈链是一种解决精确覆盖问题的实现方法，在实际应用中，我们通常把行当做选择，列当做限制。也就是说，我们有 n 种选择，m 条需要满足的限制。

本题思路

首先统计出值为 1 的格子数量 m，我们让 k = m + 4 其中 [1, m] 列为所有 1 的格子下标（因为每个值为 1 的格子属于 1 个或 0 个图形），[m + 1, k] 列为 4 个图形的下标（因为题目要求我们找出）。

然后枚举每个值为 1 的格子，查看如果以当前格子为起点，是否能摆出某个图形，如果可以，就把这个图案涉及到的几个格子都插入，再插入这个图形的列。否则，只插入当前格子自己的列。

建模完成后，我们使用舞蹈链模板求解即可。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 55, M = 500000;
struct Pos {
    int x, y;
};
char arr[N][N];
int idle = 0;
int L[M], R[M], U[M], D[M], head[M];
int cnt[N * N];
Pos pos[M];
int n, m;
int dir[4][4][4][2] = {
    { //图案
        { //旋转
            { 0, 0 }, { -1, 0 }, { -2, 0 }, { 0, 1 } //坐标偏移
        },
        {
            { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 }
        },
        {
            { 0, 0 }, { 0, -1 }, { 1, 0 }, { 2, 0 }
        },
        {
            { 0, 0 }, { -1, 0}, { 0, -1 }, { 0, -2 }
        }
    },
    {
        {
            { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 }
        },
        {
            { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }
        },
        {
            { 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 }
        },
        {
            { 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }
        }
    },
    {
        {
            { 0, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 }
        },
        {
            { 0, 0 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
        },
        {
            { 0, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }
        },
        {
            { 0, 0 }, { 0, 1 }, { -1, 0 }, { 1, 0 }
        }
    },
    {
        {
            { 0, 0 }, { 0, 1 }, { -1, 1 }, { -1, 2 }
        },
        {
            { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 }
        },
        {
            { 0, 0 }, { 0, -1 }, { 1, -1 }, { 1, -2 }
        },
        {
            { 0, 0 }, { -1, 0 }, { -1, -1 }, { -2, -1 }
        }
    }
};
void insert(int row, int col) {
    idle++;
    cnt[col]++;
    pos[idle] = { row, col };
    U[idle] = U[col];
    D[U[col]] = idle;
    U[col] = idle;
    D[idle] = col;
    if (!head[row]) head[row] = L[idle] = R[idle] = idle;
    else {
        L[idle] = L[head[row]];
        R[L[head[row]]] = idle;
        L[head[row]] = idle;
        R[idle] = head[row];
    }
}
int ind[N][N] = { 0 }; //为每个 '1' 分配列
void build() {
    memset(head, 0, sizeof head);
    memset(cnt, 0, sizeof cnt);
    memset(ind, 0, sizeof ind);
    m = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (arr[i][j] == '1')
                m++, ind[i][j] = m;
    m += 4; //为四个图形分配列
    for (int i = 0; i <= m; i++) {
        L[i] = i - 1, R[i] = i + 1;
        U[i] = D[i] = i;
        pos[i] = { 0, i };
    }
    idle = m;
    L[0] = m, R[m] = 0;
    int r = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (arr[i][j] == '1') {
                for (int t = 0; t < 4; t++) //遍历每个图案
                    for (int d = 0; d < 4; d++) { //遍历每个角度
                        bool f = true;
                        for (int c = 0; c < 4; c++) { //查看每个偏移
                            int dx = i + dir[t][d][c][0], dy = j + dir[t][d][c][1];
                            if (dx < 1 || dy < 1 || dx > n || dy > n || arr[dx][dy] != '1') {
                                f = false;
                                break;
                            }
                        }
                        if (f) {
                            r++;
                            insert(r, m - 3 + t);
                            for (int c = 0; c < 4; c++) {
                                int dx = i + dir[t][d][c][0], dy = j + dir[t][d][c][1];
                                insert(r, ind[dx][dy]);
                            }
                        }
                    }
                r++;
                insert(r, ind[i][j]);
            }
}
//冻结第 i 列及其关联行
void freeze(int col) {
    L[R[col]] = L[col], R[L[col]] = R[col];
    for (int i = D[col]; i != col; i = D[i])
        for (int j = R[i]; j != i; j = R[j])
            cnt[pos[j].y] --, U[D[j]] = U[j], D[U[j]] = D[j];
}
//激活第 i 列及其关联行
void active(int col) {
    L[R[col]] = R[L[col]] = col;
    for (int i = U[col]; i != col; i = U[i])
        for (int j = L[i]; j != i; j = L[j])
            cnt[pos[j].y] ++, U[D[j]] = j, D[U[j]] = j;
}
bool dance() {
    if (!R[0]) return true;
    int s = R[0];
    for (int i = R[s]; i; i = R[i])
        if (cnt[i] < cnt[s])
            s = i;
    freeze(s);
    for (int i = D[s]; i != s; i = D[i]) {
        for (int j = R[i]; j != i; j = R[j])
            freeze(pos[j].y);
        if (dance()) return true;
        for (int j = L[i]; j != i; j = L[j])
            active(pos[j].y);
    }
    active(s);
    return false;
}
int main() {
    int _;
    scanf("%d", &_);
    while (_--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf(" %c", &arr[i][j]);
        build();
        if (dance()) puts("Yes");
        else puts("No");
    }
    return 0;
}