五子棋对弈 参考代码

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

typedef long long LL;
const int maxn = 100 + 100;
int ans;
int board[maxn][maxn];

bool judge(int x, int y) {
    if (x != 4 && y != 4) {
        return true;
    }

    bool allSame = true;
    if (x == 4) {
        for (int i = 0; i < 5; ++i) {
            if (board[i][y] != board[x][y]) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return false;
        }
    }

    allSame = true;
    if (y == 4) {
        for (int i = 0; i < 5; ++i) {
            if (board[x][i] != board[x][y]) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return false;
        }
    }

    allSame = true;
    if (x == 4 && y == 0) {
        for (int i = 0; i < 5; ++i) {
            if (board[i][4 - i] != board[4][0]) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return false;
        }
    }

    allSame = true;
    if (x == 4 && y == 4) {
        for (int i = 0; i < 5; ++i) {
            if (board[i][i] != board[4][4]) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return false;
        }
    }

    return true;
}

void dfs(int depth, int white, int black) {
    if (depth == 25) {
        ++ans;
        return ;
    }
    int x = depth / 5;
    int y = depth % 5;
    if (white > 0) {
        board[x][y] = 0;
        if (judge(x, y)) {
            dfs(depth + 1, white - 1, black);
        }
    }
    if (black > 0) {
        board[x][y] = 1;
        if (judge(x, y)) {
            dfs(depth + 1, white, black - 1);
        }
    }
}

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

    dfs(0, 13, 12);
    cout << ans << endl;

    return 0;
}