1. 2022: [蓝桥杯2022初赛] 灭鼠先锋

传送门：http://oj.ecustacm.cn/problem.php?id=2022

1.1. 题意

在$2$行$4$列的棋盘中，两人轮流操作，每次可选择在空位上放置$1$个棋子，或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在$4$种初始局面如下所示，$O$表示空，$X$表示已放置。每人均以最优策略放棋子。判断先手胜利（输出$V$）还是后手胜利（输出$L$）。

XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO

1.2. Tag

博弈

1.3. 难度

☆☆☆

1.4. 思路

博弈题核心：

只能转移到必胜态的，均为必败态。

可以转移到必败态的，均为必胜态。

1. 首先确定最终的必败态：只剩下$1$个棋子的时候肯定是必败的。

   OXXX    XOXX
   XXXX    XXXX
   

2. 利用上述提到的核心，倒推出其他情况属于必败态还是必胜态。

3. 注意，给定的$4$个局面为先手第一步的四种局面，对于此时局面为必胜态，表示的是后手胜。

#include<bits/stdc++.h>
using namespace std;
///判断是否仅存在一个空格
bool check(string s){
    int tot = 0;
    for(auto x : s)if(x == 'O')
        tot++;
    return tot == 1;
}
map<string, bool>SG;
bool dfs(string s){
    if(SG.count(s))
        return SG[s];
    if(check(s))
        return SG[s] = false;
    ///模拟放1个棋子
    for(int i = 0; i < s.size(); i++)if(s[i] == 'O')
    {
        string tmp = s;
        tmp[i] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///模拟放2个棋子
    for(int i = 0; i < s.size() - 1; i++)if(s[i] == 'O' && s[i + 1] == 'O' && i != 3)
    {
        string tmp = s;
        tmp[i] = tmp[i + 1] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///运行到此，说明只能转移到必胜态，此时为必败态
    return SG[s] = false;
}

int main(){
    string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};
    for(int i = 0; i < 4; i++)
    {
        if(dfs(s[i]))cout<<"L";///此时为必胜态，说明后手面临的局面必胜，输出L
        else cout<<"V";
    }
    return 0;
}