[ABC219]E

题意就是给你一个4*4的网格，之后网格上有一些格子被染色了。问你有多少种选择方案，使得选的所有格子包括所有被染色的格子，之后你选的格子要是一个连通块。

attention:  不能是空心的连通块（出现回这种形状）

首先我们看之后16个格子，自然就想到2^16次暴力枚举。之后check可不可行就行了。

所以我们需要写三个check

1. 是否包含所有的染色格子

2. 是否是一个连通块

3. 是否是一个回

为了减少码量我就写了非递归DFS。关于判断是否是一个回我们只需要判断是不是所有0的连通块都与外部接触就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f; ///1061109567
const int maxn = 2e6 + 10;

int housePos[5][5];
int curOpt[5][5];
int vis[5][5];
int dic[4][2] = {1,0, 0,1, -1,0, 0,-1};

bool check1() { ///判断是否包含
    for (int i = 1; i <= 4; ++ i)
        for (int j = 1; j <= 4; ++ j)
            if (!curOpt[i][j] && housePos[i][j]) return 1;
    return 0;
}

bool check2() { ///判断是否只有一个连通块
    memset(vis, 0, sizeof vis);
    stack<pii> sta;
    for (int i = 1; i <= 4 && !sta.size(); ++ i) {
        for (int j = 1; j <= 4 && !sta.size(); ++ j) {
            if (curOpt[i][j]) sta.push({i, j});
        }
    }
    while (sta.size()) {
        pii pos = sta.top(); sta.pop();
        int x = pos.first, y = pos.second;
        if (vis[x][y]) continue;
        vis[x][y] = 1;
        for (int k = 0; k < 4; ++ k) {
            int tx = x + dic[k][0];
            int ty = y + dic[k][1];
            if (tx < 1 || ty < 1 || tx > 4 || ty > 4 || vis[tx][ty]) continue;
            if (curOpt[tx][ty] == 0) continue;
            sta.push({tx, ty});
        }
    }
    for (int i = 1; i <= 4; ++ i) {
        for (int j = 1; j <= 4; ++ j) {
            if (vis[i][j] != curOpt[i][j]) return 1;
        }
    }
    return 0;
}

bool check3() { ///判断是否有回 （0的连通块是否都触碰到边界）
    memset(vis, 0, sizeof vis);
    stack<pii> sta;
    for (int i = 1; i <= 4; ++ i) {
        for (int j = 1; j <= 4; ++ j) {
            if (!vis[i][j] && !curOpt[i][j]) {
                sta.push({i, j});
                int flag = 0; ///是否触碰到边界
                while (sta.size()) {
                    pii pos = sta.top(); sta.pop();
                    int x = pos.first, y = pos.second;
                    if (vis[x][y]) continue;
                    vis[x][y] = 1;
                    for (int k = 0; k < 4; ++ k) {
                        int tx = x + dic[k][0];
                        int ty = y + dic[k][1];
                        if (tx < 1 || ty < 1 || tx > 4 || ty > 4) {
                            flag = 1;
                            continue;
                        }
                        if (vis[tx][ty] || curOpt[tx][ty] == 1) continue;
                        sta.push({tx, ty});
                    }
                }

                if (flag == 0) return 1;
            }
        }
    }
    return 0;
}

int main() {
    for (int i = 1; i <= 4; ++ i) {
        for (int j = 1; j <= 4; ++ j) {
            scanf("%d", &housePos[i][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < (1<<16); ++ i) {
        memset(curOpt, 0, sizeof curOpt);
        for (int j = 0; j < 16; ++ j) {
            int x = j / 4 + 1;
            int y = j % 4 + 1;
            curOpt[x][y] = (i >> j) & 1;
        }
        if (check1() || check2() || check3()) continue;
        ans ++;
    }
    printf("%d
", ans);
    return 0;
}