题解 | #弹珠游戏#

牛魔太难写了, 尤其是坐标映射

将原来的菱形转化为矩形然后分类讨论, 记忆化搜索

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int hx[] = {-2, -2, -1, -1, 1, 1, 2, 2}, hy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

vector<int> p = {0, 4, 1, 8, 5, 2, 12, 9, 6, 3, 13, 10, 7, 14, 11, 15};

void solve() {
    int st = 0;
    for (int i = 0; i < 16; ++i) {
        char c;
        cin >> c;
        if (c == '*') st |= (1 << p[i]);
    }

    vector<int> f(1 << (16), -1);

    auto chk = [&](int idx, int d) {
        if (d == 1) return (idx == 3 || idx == 7 || idx == 11 || idx == 15);
        if (d == 3) return (idx == 0 || idx == 4 || idx == 8 || idx >= 12);
        if (d == 4) return (idx >= 12);
        if (d == 5) return (idx == 3 || idx == 7 || idx == 11 || idx >= 12);
        return false;
    };

    vector<int> dir = {1, 3, 4, 5};
    auto dfs = [&](auto dfs, int s) -> int { 
        if (f[s] != -1) return f[s];
        if (s == (1 << 16) - 1) return 0;

        for (int i = 0; i < 16; ++i) {
            if (s >> i & 1) continue;
            for (int d : dir) {
                int t = s;
                for (int c = 0; c < 3; ++c) {
                    // idx 是走到的位置
                    int idx = i + d * c;
                    if (idx > 15) break;
                    if (t & (1 << idx)) break;
                    t |= (1 << idx);

                    // 如果交给对手的局面是必败态那么当前就是必胜态
                    if (!dfs(dfs, t)) return f[s] = 1;
                    if (chk(idx, d)) break;
                }
            }    
        }

        // 不是必胜态就是必败态
        return f[s] = 0;
    };

    if (dfs(dfs, st)) cout << "Alice" << '\n';
    else cout << "Bob" << '\n';

/**/ #ifdef LOCAL
                     cout
                      << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}