【蓝桥杯】灭鼠先锋

一.题目描述

 二.解题思路

博弈论：

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

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

最优的策略是，下一步一定是必败态。

#include<iostream>
#include<map>
using namespace std;map<string,bool> mp;
bool check(string s){int cnt=0;for(int i=0;i<s.length();i++){if(s[i]=='o'){cnt++;}}return cnt==1;
}
bool dfs(string s){if(mp.count(s)){return mp[s];}if(check(s)){//当前状态只有一个o，必为必败态mp[s]=false;return false;}//放置1个for(int i=0;i<s.size();i++){if(s[i]=='o'){string temp=s;temp[i]='x';if(dfs(temp)==false){mp[s]=true;return true;}}}//放置2个for(int i=0;i<s.size();i++){if(s[i]=='o'&&s[i+1]=='o'&&i!=3){string temp=s;temp[i]='x';temp[i+1]='x';if(dfs(temp)==false){mp[s]=true;return true;}}}mp[s]=false;return false;
}

 只要能够确保当前棋局的状态在自己下过棋之后，能够是必败，则一定必胜。

使用键值对来记录状态。（动态规划）

如果对于当前的棋盘状态，以前有记录的话，可以直接查询。

当前状态，棋盘上只有一个o，那么一定是必败态，递归的出口之一。

如果可以继续下棋，那么就要找出最优方案（下一步一定是必败态的）。

可以选择放置一个或两个棋子。

对于整个棋盘进行遍历，找到所有能够下棋子的位置，进行探索，如果将棋子下在该处，其下一个状态为必败态，则这个状态就一定是必胜态，返回true。

如果已经探索了所有的位置，但是仍然没有返回，那么就说明，现在一定是必败。