1. 2022: [蓝桥杯2022初赛] 灭鼠先锋

传送门:http://oj.ecustacm.cn/problem.php?id=2022

1.1. 题意

列的棋盘中,两人轮流操作,每次可选择在空位上放置个棋子,或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在种初始局面如下所示,表示空,表示已放置。每人均以最优策略放棋子。判断先手胜利(输出)还是后手胜利(输出)。

XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO

1.2. Tag

博弈

1.3. 难度

☆☆☆

1.4. 思路

博弈题核心:

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

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

  1. 首先确定最终的必败态:只剩下个棋子的时候肯定是必败的。

    OXXX    XOXX
    XXXX    XXXX
    
  2. 利用上述提到的核心,倒推出其他情况属于必败态还是必胜态。

  3. 注意,给定的个局面为先手第一步的四种局面,对于此时局面为必胜态,表示的是后手胜。

#include<bits/stdc++.h>
using namespace std;
///判断是否仅存在一个空格
bool check(string s){
    int tot = 0;
    for(auto x : s)if(x == 'O')
        tot++;
    return tot == 1;
}
map<string, bool>SG;
bool dfs(string s){
    if(SG.count(s))
        return SG[s];
    if(check(s))
        return SG[s] = false;
    ///模拟放1个棋子
    for(int i = 0; i < s.size(); i++)if(s[i] == 'O')
    {
        string tmp = s;
        tmp[i] = 'X';
        if(dfs(tmp) == false)///可以到达必败态均为必胜态
            return SG[s] = true;
    }
    ///模拟放2个棋子
    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 SG[s] = true;
    }
    ///运行到此,说明只能转移到必胜态,此时为必败态
    return SG[s] = false;
}

int main(){
    string s[] = {"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};
    for(int i = 0; i < 4; i++)
    {
        if(dfs(s[i]))cout<<"L";///此时为必胜态,说明后手面临的局面必胜,输出L
        else cout<<"V";
    }
    return 0;
}

results matching ""

    No results matching ""