【蓝桥杯】灭鼠先锋

一.题目描述

 二.解题思路

博弈论：

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

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

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

#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。

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