题解 | 弹珠游戏

#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;
}

	
	

		'''
	

	

		Hala Madrid!
	

	

		https://github.com/USYDDonghaoLi/Programming_Competition
	

	

		'''
	

	

		import sys
	

	

		import os
	

	

		from io import BytesIO, IOBase
	

	

		BUFSIZE = 8192
	

	

		class FastIO(IOBase):
	

	

		    newlines = 0
	

	

		    def __init__(self, file):
	

	

		        self._fd = file.fileno()
	

	

		        self.buffer = BytesIO()
	

	

		        self.writable = "x" in file.mode or "r" not in file.mode
	

	

		        self.write = self.buffer.write if self.writable else None
	

	

		    def read(self):
	

	

		        while True:
	

	

		            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
	

	

		            if not b:
	

	

		                break
	

	

		            ptr = self.buffer.tell()
	

	

		            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
	

	

		        self.newlines = 0
	

	

		        return self.buffer.read()
	

	

		    def readline(self):
	

	

		        while self.newlines == 0:
	

	

		            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
	

	

		            self.newlines = b.count(b"\n") + (not b)
	

	

		            ptr = self.buffer.tell()
	

	

		            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
	

	

		        self.newlines -= 1
	

	

		        return self.buffer.readline()
	

	

		    def flush(self):
	

	

		        if self.writable:
	

	

		            os.write(self._fd, self.buffer.getvalue())
	

	

		            self.buffer.truncate(0), self.buffer.seek(0)
	

	

		class IOWrapper(IOBase):
	

	

		    def __init__(self, file):
	

	

		        self.buffer = FastIO(file)
	

	

		        self.flush = self.buffer.flush
	

	

		        self.writable = self.buffer.writable
	

	

		        self.write = lambda s: self.buffer.write(s.encode("ascii"))
	

	

		        self.read = lambda: self.buffer.read().decode("ascii")
	

	

		        self.readline = lambda: self.buffer.readline().decode("ascii")
	

	

		sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
	

	

		input = lambda: sys.stdin.readline().rstrip("\r\n")
	

	

		def I():
	

	

		    return input()
	

	

		def II():
	

	

		    return int(input())
	

	

		def MI():
	

	

		    return map(int, input().split())
	

	

		def LI():
	

	

		    return list(input().split())
	

	

		def LII():
	

	

		    return list(map(int, input().split()))
	

	

		def GMI():
	

	

		    return map(lambda x: int(x) - 1, input().split())
	

	

		#------------------------------FastIO---------------------------------
	

	

		from bisect import *
	

	

		from heapq import *
	

	

		from collections import *
	

	

		from functools import *
	

	

		from itertools import *
	

	

		from time import *
	

	

		from random import *
	

	

		from math import log, gcd, sqrt, ceil
	

	

		from types import GeneratorType
	

	

		def bootstrap(f, stack=[]):
	

	

		    def wrappedfunc(*args, **kwargs):
	

	

		        if stack:
	

	

		            return f(*args, **kwargs)
	

	

		        else:
	

	

		            to = f(*args, **kwargs)
	

	

		            while True:
	

	

		                if type(to) is GeneratorType:
	

	

		                    stack.append(to)
	

	

		                    to = next(to)
	

	

		                else:
	

	

		                    stack.pop()
	

	

		                    if not stack:
	

	

		                        break
	

	

		                    to = stack[-1].send(to)
	

	

		            return to
	

	

		    return wrappedfunc
	

	

		# seed(19981220)
	

	

		# RANDOM = getrandbits(64)
	

	

		 
	

	

		# class Wrapper(int):
	

	

		#     def __init__(self, x):
	

	

		#         int.__init__(x)
	

	

		#     def __hash__(self):
	

	

		#         return super(Wrapper, self).__hash__() ^ RANDOM
	

	

		# def TIME(f):
	

	

		#     def wrap(*args, **kwargs):
	

	

		#         s = perf_counter()
	

	

		#         ret = f(*args, **kwargs)
	

	

		#         e = perf_counter()
	

	

		#         print(e - s, 'sec')
	

	

		#         return ret
	

	

		   
	

	

		#     return wrap
	

	

		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
	

	

		    empty_line = I()
	

	

		    A = transform(A)
	

	

		    A = encode(A)
	

	

		    f(A)
	

	

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

	

		for testcase in range(II()):
	

	

		    solve(testcase)
	

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