黑白棋 参考代码

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

typedef long long LL;
const int maxn = 10 + 100;
int maskRow[maxn], maskCol[maxn];
int n = 6;
string str[maxn] = {
    "10.0..",
    "...0..",
    "....00",
    "......",
    "..1..1",
    ".0..1."
};

bool judgeCol(int x, int y) {
    for (int i = 0; i < y; ++i) {
        if (maskCol[i] == maskCol[y]) {
            return false;
        }
    }
    return __builtin_popcount(maskCol[y]) == 3;
}

bool judgeRow(int x, int y) {
    for (int i = 0; i < x; ++i) {
        if (maskRow[i] == maskRow[x]) {
            return false;
        }
    }
    return __builtin_popcount(maskRow[x]) == 3;
}


bool dfs(int depth);

bool markAndDfs(int x, int y, int mark) {
    char ch = str[x][y];
    str[x][y] = (mark + '0');
    maskRow[x] |= (mark << y);
    maskCol[y] |= (mark << x);
    bool colFlag = (x < 2 ||
                    (__builtin_popcount((maskCol[y] >> (x - 2)) & 7) != 0 &&
                     __builtin_popcount((maskCol[y] >> (x - 2)) & 7) != 3));
    if (x == n - 1) {
        colFlag = colFlag && judgeCol(x, y);
    }
    bool rowFlag = (y < 2 || (
                        __builtin_popcount((maskRow[x] >> (y - 2)) & 7) != 0 &&
                        __builtin_popcount((maskRow[x] >> (y - 2)) & 7) != 3));
    if (y == n - 1) {
        rowFlag = rowFlag && judgeRow(x, y);
    }
    if (colFlag && rowFlag) {
        if (dfs(x * n + y + 1)) {
            return true;
        }
    }
    str[x][y] = ch;
    maskRow[x] &= ~(1 << y);
    maskCol[y] &= ~(1 << x);
    return false;
}

bool dfs(int depth) {
    int x = depth / n;
    int y = depth % n;
    if (depth == 36) {
        for (int i = 0; i < n; ++i) {
            cout << str[i] << endl;
        }
        cout << endl;
        return true;
    }
    if (str[x][y] == '.') {
        if (markAndDfs(x, y, 0)) {
            return true;
        }
        if (markAndDfs(x, y, 1)) {
            return true;
        }
        return false;
    }
    if (str[x][y] == '0') {
        return markAndDfs(x, y, 0);
    }
    return markAndDfs(x, y, 1);
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc

    dfs(0);

    return 0;
}