©2020-2024 ioDraw All rights reserved
题目描述：
题解思路：
首先要明白两种状态：必胜态与必败态
必胜态：当前状态为必胜态，意思就是说，你有一种走法可以将当前局面的状态转向必败态（对手所面临的状态）
，因为题中说明，游戏双方会按照自己的最优策略来游戏，既然有一种方法可以使得对手所面临的的状态为必败态，那么一定会这样走。
必败态：当前游戏方所面临的状态为必败态，无论怎么走棋，只能将下一个状态转化为必胜态（对手一定会胜利）。
如果在深度搜索的过程中，可以找到必败态的话，那么当前状态为必胜态
如若不能的话，当前的状态只能是必败态
题解代码：
//灭鼠先锋游戏 //首先一定要明白什么是必胜态与必败态 #include <bits/stdc++.h> using namespace std;
map<string,bool> pp; //判断该字符串是否只有一个 bool isone0(string s) { int num=0; for(int
i=0;i<s.length();++i){ if(s[i]== 'O') num++; //只有一个棋子了，那么就是必败态 } if(num==1)
return true; //其他情况不做处理，因为判断不出来 // int tot = 0; // for(auto x:s) if(x=='O')
tot++; // return tot == 1; } bool dfs(string s) { //判断出结束条件，就是只有一个空格了，一定是必败态
if(isone0(s)) // pp[s] = false; return pp[s] = false; //if(isone0(s)) return
pp[s] = false; // 当棋盘只剩一个棋子 //判断这个状态是否已经存在 if(pp.count(s)==1) return pp[s];
//返回1表示可以找到 //开始走棋 //第一种情况，走1步棋子 for(int i=0;i<s.size();++i) { if(s[i]=='O'){
string temp2 = s; temp2[i] = 'X'; if(dfs(temp2) == false)
//如果可以到达必败态，那么一定是必胜态可以返回了 return pp[s] = true; } } //第二种情况，走两步棋子 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 pp[s] = true; } } return pp[s] = false;
//如果没能遇到必胜态，就是必败态 } int main(){ string
ss[4]={"XOOOOOOO","XXOOOOOO","OXOOOOOO","OXXOOOOO"}; //小蓝下完一步棋后的状态
//开始对每一种情况进行深搜 for(int i=0;i<4;++i){ string s = ss[i]; if(dfs(s) == false) {
cout<<"V"; //返回值是bool类型的，如果为真，此状态就是必胜态 } else { cout<<"L"; } } return 0; }
但是有一个问题就是：
为什么：if(isone0(s)) return pp[s] = false; // 当棋盘只剩一个棋子
不能替换为下面这种写法
if(isone0(s)) pp[s] = false; return pp[s] = false;