成都招聘网站建设,建网站的优势,什么网站可以做效果图,python编程语言大全一.题目描述 二.解题思路 博弈论#xff1a; 只能转移到必胜态的#xff0c;均为必败态。 可以转移到必败态的#xff0c;均为必胜肽。 最优的策略是#xff0c;下一步一定是必败态。
#includeiostream
#includemap
using namespace std;mapstring,bo…一.题目描述 二.解题思路 博弈论 只能转移到必胜态的均为必败态。 可以转移到必败态的均为必胜肽。 最优的策略是下一步一定是必败态。
#includeiostream
#includemap
using namespace std;mapstring,bool mp;
bool check(string s){int cnt0;for(int i0;is.length();i){if(s[i]o){cnt;}}return cnt1;
}
bool dfs(string s){if(mp.count(s)){return mp[s];}if(check(s)){//当前状态只有一个o必为必败态mp[s]false;return false;}//放置1个for(int i0;is.size();i){if(s[i]o){string temps;temp[i]x;if(dfs(temp)false){mp[s]true;return true;}}}//放置2个for(int i0;is.size();i){if(s[i]os[i1]oi!3){string temps;temp[i]x;temp[i1]x;if(dfs(temp)false){mp[s]true;return true;}}}mp[s]false;return false;
} 只要能够确保当前棋局的状态在自己下过棋之后能够是必败则一定必胜。
使用键值对来记录状态。动态规划
如果对于当前的棋盘状态以前有记录的话可以直接查询。
当前状态棋盘上只有一个o那么一定是必败态递归的出口之一。
如果可以继续下棋那么就要找出最优方案下一步一定是必败态的。
可以选择放置一个或两个棋子。
对于整个棋盘进行遍历找到所有能够下棋子的位置进行探索如果将棋子下在该处其下一个状态为必败态则这个状态就一定是必胜态返回true。
如果已经探索了所有的位置但是仍然没有返回那么就说明现在一定是必败。
