1. 2022: [蓝桥杯2022初赛] 灭鼠先锋
传送门:http://oj.ecustacm.cn/problem.php?id=2022
1.1. 题意
在行列的棋盘中,两人轮流操作,每次可选择在空位上放置个棋子,或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。
先手存在种初始局面如下所示,表示空,表示已放置。每人均以最优策略放棋子。判断先手胜利(输出)还是后手胜利(输出)。
XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO
1.2. Tag
博弈
1.3. 难度
☆☆☆
1.4. 思路
博弈题核心:
只能转移到必胜态的,均为必败态。
可以转移到必败态的,均为必胜态。
首先确定最终的必败态:只剩下个棋子的时候肯定是必败的。
OXXX XOXX XXXX XXXX
利用上述提到的核心,倒推出其他情况属于必败态还是必胜态。
注意,给定的个局面为先手第一步的四种局面,对于此时局面为必胜态,表示的是后手胜。
#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;
}