题目描述:

题解思路:

 首先要明白两种状态:必胜态与必败态

必胜态:当前状态为必胜态,意思就是说,你有一种走法可以将当前局面的状态转向必败态(对手所面临的状态)
,因为题中说明,游戏双方会按照自己的最优策略来游戏,既然有一种方法可以使得对手所面临的的状态为必败态,那么一定会这样走。

必败态:当前游戏方所面临的状态为必败态,无论怎么走棋,只能将下一个状态转化为必胜态(对手一定会胜利)。

如果在深度搜索的过程中,可以找到必败态的话,那么当前状态为必胜态

如若不能的话,当前的状态只能是必败态

题解代码:
//灭鼠先锋游戏 //首先一定要明白什么是必胜态与必败态 #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;

技术
今日推荐
阅读数 155
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信