题解 | 弹珠游戏

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

const int N = 1 << 16;
int res[N];
unordered_set<int> available;

int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};

void f(int state) {
    if (res[state] != -1) return;
    int flag = 0;
    for (auto avail : available) {
        if ((state & avail) == 0) {
            int newstate = state ^ avail;
            f(newstate);
            if (res[newstate] == 0) {
                flag = 1;
                break;
            }
        }
    }
    res[state] = flag;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    memset(res, -1, sizeof(res));
    res[(1 << 16) - 1] = 0;
    
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            for (int dir = 0; dir < 8; dir++) {
                int cx = x, cy = y;
                int curstate = 0;
                for (int k = 0; k < 3; k++) {
                    curstate |= (1 << (cx * 4 + cy));
                    available.insert(curstate);
                    cx += dx[dir];
                    cy += dy[dir];
                    if (cx < 0 || cx >= 4 || cy < 0 || cy >= 4) break;
                }
            }
        }
    }
    
    int T;
    cin >> T;
    int rowlen[7] = {1, 2, 3, 4, 3, 2, 1};
    for (int test = 0; test < T; test++) {
        vector<vector<char>> A(7);
        for (int i = 0; i < 7; i++) {
            A[i].resize(rowlen[i]);
            for (int j = 0; j < rowlen[i]; j++) {
                string s;
                cin >> s;
                A[i][j] = s[0];
            }
        }
        vector<vector<char>> grid(4, vector<char>(4));
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4 - i; j++) {
                grid[i][j] = A[i + j][i];
            }
            for (int j = 4 - i; j < 4; j++) {
                grid[i][j] = A[i + j][3 - j];
            }
        }
        int state = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (grid[i][j] == '*') {
                    state |= (1 << (i * 4 + j));
                }
            }
        }
        f(state);
        cout << (res[state] ? "Alice" : "Bob") << "\n";
    }
    return 0;
}

inf = float('inf')

fmin = lambda x, y: x if x < y else y
fmax = lambda x, y: x if x > y else y

def transform(A):
    res = [['' for _ in range(4)] for _ in range(4)]

    for i in range(4):
        for j in range(4 - i):
            res[i][j] = A[i + j][i]
            
        for j in range(4 - i, 4):
            res[i][j] = A[i + j][3 - j]
            
    return res

def encode(A):
    res = 0
    for i in range(4):
        for j in range(4):
            if A[i][j] == '*':
                bit = i * 4 + j
                res |= 1 << bit

    return res

d = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1))

available = set()

for x in range(4):
    for y in range(4):
        for dx, dy in d:
            cx, cy = x, y
            curstate = 0
            for _ in range(3):
                curstate |= 1 << (cx * 4 + cy)
                available.add(curstate)
                cx += dx
                cy += dy

                if 0 <= cx < 4 and 0 <= cy < 4:
                    continue
                else:
                    break


res = [-1 for _ in range(1 << 16)]
res[-1] = 0

@bootstrap
def f(state):
    if res[state] != -1:
        yield None
    
    flag = 0

    for avail in available:
        if not state & avail:
            newstate = state ^ avail
            if res[newstate] == -1:
                yield f(newstate)
            if not res[newstate]:
                flag = 1
                break
    
    res[state] = flag
    yield None


# @TIME
def solve(testcase):
    A = [LI() for _ in range(7)]
    assert len(A[0]) == 1 and len(A[1]) == 2 and len(A[2]) == 3 and len(A[3]) == 4 and len(A[4]) == 3 and len(A[5]) == 2 and len(A[6]) == 1
    A = transform(A)
    A = encode(A)

    f(A)

    print("Alice" if res[A] else "Bob")

for testcase in range(II()):
    solve(testcase)

把每个棋盘转换成4*4的矩阵，把矩阵的状态转换为二进制状态，之后进行记忆化搜索。

本来写的Python过不去，可能是因为数据不都是7行。