T3 弹珠游戏

· · 题解

题目链接

本题是一道博弈论的题目，需要确定给定的某个状态是必胜态还是必败态，可以使用递归加备忘的方式予以确定。

初看似乎给定的棋盘和放置方式难以处理，实际上，只需将棋盘逆时针（或顺时针）旋转45度，所得到的就是一个水平方向的棋盘，在水平方向的棋盘上处理就容易得多了。在读入数据时对棋盘进行一个简单的位置映射即可。

为了便于解题，将棋盘的状态转换为一个二进制数。方法：放置弹珠的位置对应的二进制位为 1，未放置弹珠的位置对应的二进制位为 0。容易知道，当棋盘放满弹珠时，对于 \operatorname{Alice} 来说是必败态，即 dp[(1 << 16) - 1] = 0;。接着通过递归来确定当前状态所对应的整数 x 是必胜态还是必败态。

如果棋盘的某个位置为空，那么从此位置开始向右、向下、向右下三个方向逐次检查，是否能连续放置 1 颗、2 颗、3 颗弹珠，如果能够放置，则将对应的二进制位置为 1。对于状态 x 的所有后继状态来说，如果有至少一个后继状态 y 是必败态，那么表明当前状态 x 是必胜态，即 dp[x] = 1;。如果检查所有的后继状态均为必胜态，那么当前状态 x 为必败态，即 dp[x] = 0;。

应用备忘技巧可以避免重复解决子问题，提高程序效率，否则很容易超时。

由于输入较多，需要应用快读以提高输入效率。

#include <bits/stdc++.h>

using namespace std;

const int LENGTH = (1 << 20);

inline int nextChar()
{
    static char buffer[LENGTH], *p = buffer, *end = buffer;
    if (p == end) {
        if ((end = buffer + fread(buffer, 1, LENGTH, stdin)) == buffer) return EOF;
        p = buffer;
    }
    return *p++;
}

inline bool nextInt(int &x)
{
    static char negative = 0, c = nextChar();
    negative = 0, x = 0;
    while ((c < '0' || c > '9') && c != '-')
    { if (c == EOF) return false; c = nextChar(); }
    if (c == '-') { negative = 1; c = nextChar(); }
    do x = (x << 3) + (x << 1) + c - '0'; while ((c = nextChar()) >= '0');
    if (negative) x = -x;
    return true;
}

int cache[1 << 16], offset[4][2] = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};

int dfs(int x)
{
    if (~cache[x]) return cache[x];
    for (int i = 0; i < 16; i++)
    {
        if (x & (1 << i)) continue;
        int r = i / 4, c = i % 4;
        for (int j = 0; j < 4; j++)
        {
            int bit = 0;
            for (int k = 0; k < 3; k++)
            {
                int rr = r + offset[j][0] * k, cc = c + offset[j][1] * k;
                if (rr < 0 || rr > 3 || cc < 0 || cc > 3) break;
                if (x & (1 << (rr * 4 + cc))) break;
                bit |= (1 << (rr * 4 + cc));
                if (!dfs(x ^ bit)) return cache[x] = 1;
            }
        }
    }
    return cache[x] = 0;
}

int matrix[16] = {0, 4, 1, 8, 5, 2, 12, 9, 6, 3, 13, 10, 7, 14, 11, 15};

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    memset(cache, -1, sizeof(cache));
    cache[(1 << 16) - 1] = 0;

    int cases;
    nextInt(cases);
    for (int cs = 1; cs <= cases; cs++)
    {
        int mask = 0, cnt = 0;
        char character;
        while (cnt < 16)
        {
            character = nextChar();
            if (character == '*' || character == '.')
            {
                if (character == '*')
                    mask |= (1 << matrix[cnt]);
                cnt++;
            }
        }
        cout << (dfs(mask) ? "Possible." : "Impossible.") << '\n';
    }

    return 0;
}