试题 历届试题 填字母游戏 博弈+dfs剪枝

#include<iostream>
#include<string>
#include<map>
using namespace std;

//输入 
int n;
string str;//当前状态 

map<string,int> m;//键值对 用来把相同状况剪枝

int dfs(string str)// 返回  1 0 -1
{
    if( m.find(str)!=m.end() ){
        return m[str];//如果重复 剪枝 
    }
    
    if( (str.find("LO*")+1)||(str.find("*OL")+1)||(str.find("L*L")+1)){
        return m[str] = 1;//如果发现任意一个 则胜利(+1后返回值>=1 未找到返回0) 
    }
/***    上面代码如果改为 
    if( str.find("LOL") ){
        return m[str] = -1;//如果发现任意一个 则胜利(+1后返回值>=1 未找到返回0) 
    } 
        逻辑上也是对的 但运行会超时 大概是多了不必要的递归  ***/
    if( str.find(‘*‘)==-1 ){
        return m[str] = 0;//没有空位* 则平局 
    }
    
    int flat = -1;
    for(int i=0; i<str.length(); i++)
    {
        if( str[i] != ‘*‘ )
        {
            continue;
        }
        //尝试两种方式 
        str[i] = ‘L‘;
        if( dfs(str)==-1 ){
            str[i] = ‘*‘;//这里要先回溯为传入时的状态 再存入map 
            return m[str] = 1;
        }
        
        if( dfs(str)==0 ){
            flat = 0;
        }
        
        str[i] = ‘O‘;
        if( dfs(str)==-1 ){
            str[i] = ‘*‘;
            return m[str] = 1;
        }
        
        if( dfs(str)==0 ){
            flat = 0;
        }
        
        str[i] = ‘*‘;//回溯 
    }
    
    return m[str] = flat;
}

void solve()
{
    int res = dfs(str);
    cout<<res<<endl;
}

int main()
{
    cin>>n;
    while( n-- )
    {
        cin>>str;
        solve();
    }
    return 0;
}