洛谷P7395 弹珠游戏题解

题目链接：P7395 弹珠游戏（2021 CoE-I C）

题意：

$\operatorname{Alice}$ 对弹珠游戏已经有些厌烦了，她经常在电脑上玩这个游戏。她之所以感到厌烦是因为在这个游戏上她已经是专家级别，她总是能够和电脑打成平手。$\operatorname{Bob}$ 为 $\operatorname{Alice}$ 创造了一款新的电脑游戏。以下是这款两人电脑游戏的规则：

（1）游戏在如下图所示的菱形棋盘上进行；

（2）两名玩家轮流放置弹珠，可以在横向、纵向、$45$ 度斜线、$135$ 度斜线方向未放置弹珠的位置连续放置 $1$ 至 $3$ 颗弹珠，玩家在可以放置弹珠的情况下，必须至少放置 $1$ 颗弹珠。以下是合法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：

以下是非法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：

非法原因的解释：（$a$）三颗弹珠不在同一条斜线（或者垂直线）上；（$b$）两颗弹珠之间相隔一个空位；（$c$）三颗弹珠不在同一条斜线上；（$d$）三颗弹珠不在同一条斜线（或者垂直线）上；（$e$）一次性放置了 $4$ 颗弹珠；（$f$）三颗弹珠不在同一条水平线（或者垂直线、或者斜线）上。

（3）如果某位玩家无法再继续放置弹珠，则该名玩家输掉游戏，另外一名玩家获胜。

$\operatorname{Alice}$ 总是第一个进行游戏，而且经常是和 $\operatorname{Bob}$ 玩这个游戏，$\operatorname{Bob}$ 在进行若干游戏操作后可能会离开，将游戏交由电脑代理，电脑总是按照最优策略放置弹珠。
给定 $\operatorname{Bob}$ 离开后的游戏状态，你的任务是确定 $\operatorname{Alice}$ 是否可能在对阵电脑时获得胜利。

输入格式：

输入第一行包含一个整数 $T$，表示测试数据的组数。接着是一个空行。再接下来是 $T$ 组表示棋盘状态的数据，每组数据由七行字符构成，表示 $\operatorname{Bob}$ 离开后的游戏状态，* 表示该位置已经放置了弹珠，. 表示该位置未放置弹珠。相邻两组测试数据之间有一个空行。

输出格式：

对于每组测试数据，如果 $\operatorname{Alice}$ 能够获胜，输出 Possible.，否则输出 Impossible.。

数据范围：

对于 $100\%$ 的数据，$0 \lt T \leq 10^6$。

首先把棋盘转 $45^{\circ}$ ，便于处理。

一眼博弈论，注意到棋盘大小很小，考虑记忆化搜索处理

设 $f_S$ 表示状态为 $S$ 时是否先手必胜，转移枚举空位暴力填。

由于往左下填和往右上填本质是一致的，所以我们只需要枚举「左下」「下」「右下」「右」即可。

小细节，填三个可以从填两个的再补上一个，写的时候直接或一下就好了。

时间复杂度 $\mathcal{O}(2^{16} + T)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)((1 << 16) + 15))

signed char f[N];

// -, |, \, / 
const int dx[5] = {0, 1, 1, 1};
const int dy[5] = {1, 0, 1, -1};
const int idx[20] = {0,4,1,8,5,2,12,9,6,3,13,10,7,14,11,15};

int dfs(int u)
{
    if(~f[u]) return f[u];
    for(int i = 0; i < 16; i++)
    {
        if((u >> i) & 1) continue;
        int x = i / 4, y = i % 4;
        for(int j = 0; j < 4; j++)
        {
            int bit = 0;
            for(int k = 0; k < 3; k++)
            {
                int tx = x + dx[j] * k, ty = y + dy[j] * k;
                if(tx < 0 || ty < 0 || tx > 3 || ty > 3) break;
                if(u >> (tx * 4 + ty) & 1) break;
                bit |= (1 << (tx * 4 + ty));
                if(!dfs(u ^ bit)) return f[u] = 1;
            }
        }
    }
    return f[u] = 0;
}
void work()
{
    char ch; int bit = 0;
    for(int i = 0; i < 16; i++)
    {
        cin >> ch;
        if(ch == '*') bit |= (1 << idx[i]);
    }
    cout << (dfs(bit) ? "Possible.\n" : "Impossible.\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,-1,sizeof(f)); f[(1 << 16) - 1] = 0;
    int q; cin >> q; while(q--) work();
    return 0;
}