import sys
input=sys.stdin.readline
from functools import lru_cache

limit = {
    1: {3 ,7 ,11,15},
    3: {0 ,4 ,8 ,12,13,14,15},
    4: {12,13,14,15},
    5: {3 ,7 ,11,12,13,14,15}
}

@lru_cache(maxsize=None)
def dfs(state):  # 16bit状态，但是每个bit映射成正方形比较好，要不有种淡淡的绝望感
    if state == (1 << 16)-1:
        return False  # 对于这种全填满局面，当前人会败
    for i in range(16):
        if state & (1 << i):
            continue # 已经有，则跳过
        # 四种方向+4 +1 +5 +3，三种数量 1 2 3，别人失败我必胜
        for d in [1,3,4,5]:
            t = state
            for _ in range(3):
                idx = i+d*_
                if idx >= 16 or idx < 0:
                    break  # 超出跳过
                if t & (1 << idx):
                    break  # 已经有，则跳过
                t |= (1 << idx)
                if not dfs(t):
                    return True
                if idx in limit[d]:break
    return False


pos = [[0], [4, 1], [8, 5, 2], [12, 9, 6, 3], [13, 10, 7], [14, 11], [15]]#映射数组
tag = False
for _ in range(int(input())):
    state = 0
    if tag:
        input()
    for i in range(7):
        for j, c in enumerate(input().split()):
            if c == "*":
                state |= 1 << pos[i][j]
    tag = True
    ans = dfs(state)
    print("Alice" if ans else "Bob")

题解：棋盘连线游戏（必胜策略分析）

题目理解

这是一个两人轮流操作的棋盘游戏，棋盘是一个菱形的4×4网格（16个位置）。游戏规则如下：

每回合，玩家必须选择一个未占用的格子作为起点
从该起点出发，沿四个方向之一（右、右上、下、右下）放置1-3个连续的格子
先无法操作（所有格子都被占满）的玩家输掉游戏

我们需要判断在给定初始棋盘状态下，先手玩家（Alice）是否有必胜策略。

核心思路

1. 状态压缩

16个格子 → 用16位二进制数表示
1表示格子已被占用，0表示空格
例如：状态state = 0b1010...表示哪些格子已被占用

2. 菱形到正方形的映射

原始的菱形不方便计算，我们将其映射为正方形：

原菱形（7行）：
    0
   1 4
  2 5 8
 3 6 9 12
  7 10 13
   11 14
    15

映射为4×4正方形：
0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15

pos数组就是完成这个映射的。

3. 方向与限制

游戏中可以沿四个方向放置连续1-3个格子：

+1：向右（→）
+3：右上（↗）
+4：向下（↓）
+5：右下（↘）

limit字典防止越界：

比如+1方向：在格子3,7,11,15不能再向右
其他方向类似，防止超出4×4边界

4. 必胜策略分析（博弈论）

这是典型的组合博弈问题，使用记忆化搜索+状态压缩：

必败局面：当前玩家操作后，对方无论怎么走都会输
必胜局面：存在一种操作，使得对方进入必败局面

具体判断：

如果棋盘全满（state == (1<<16)-1），当前玩家必败（无处可走）
否则，尝试所有可能的操作：选一个空格子作为起点沿四个方向之一，放置1-3个连续格子如果存在一种操作能让对方进入必败状态，则当前玩家必胜
如果所有操作都无法让对方必败，则当前玩家必败

代码解析

@lru_cache(maxsize=None)  # 记忆化装饰器，避免重复计算
def dfs(state):
    if state == (1 << 16)-1:  # 全满，当前玩家输
        return False
    
    for i in range(16):  # 遍历所有格子
        if state & (1 << i):  # 格子已占用，跳过
            continue
        
        # 尝试四个方向
        for d in [1, 3, 4, 5]:
            t = state  # 临时状态
            for _ in range(3):  # 最多放3个格子
                idx = i + d * _  # 计算下一个格子位置
                
                # 检查是否合法
                if idx >= 16 or idx < 0:  # 越界
                    break
                if t & (1 << idx):  # 格子已占用
                    break
                
                t |= (1 << idx)  # 占用这个格子
                if not dfs(t):  # 如果对方必败
                    return True  # 当前玩家必胜
                
                if idx in limit[d]:  # 到达边界，不能继续
                    break
    
    return False  # 所有操作都无法让对方必败，当前玩家必败

算法复杂度

状态总数：2¹⁶ = 65536 种（可接受）
每个状态最多尝试 16(起点) × 4(方向) × 3(长度) ≈ 192 种操作
使用记忆化后，每个状态只计算一次
总时间复杂度：O(状态数 × 操作数) ≈ 1.2×10⁷，可以接受

输入输出说明

输入格式：

第一行：测试用例数 T
每个测试用例：7行，每行用空格分隔的字符 "*"表示占用"."表示空格
测试用例之间有空行

输出格式：

对每个测试用例，输出"Alice"（先手必胜）或"Bob"（后手必胜）

示例解释

假设初始状态：

. . * .
. * * *
* * * *
. * * .

Alice可以先选择一个合适的起点和方向，放置连续格子，迫使Bob进入必败局面。

关键点

状态压缩：16位二进制表示棋盘状态
映射转换：菱形→正方形，简化计算
边界限制：limit防止越界
记忆化搜索：避免重复计算相同状态
博弈思维：寻找让对手必败的操作

这个解法穷举所有可能状态，利用记忆化避免重复计算，是解决这类小型棋盘博弈问题的经典方法。

题解 | 弹珠游戏