2022年蓝桥杯省赛 C/C++ A组B题灭鼠先锋题解

问题描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。


灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。


小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况：

XOOO XXOO OXOO OXXO 
OOOO OOOO OOOO OOOO

其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。
请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

思路

博弈论：

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

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

• 只剩下1个棋子的时候肯定是必败的。
• 那么最优的策略是什么呢，就是你的下一步一定是必败态
• 用一维字符串方式存储二维数组

这里举一个例子
比如说 XXXXX000这种状态的下一步有XXXXXX00,XXXXXXX0,而XXXXXXX0是必败的状态，所以我们必然会采用XXXXXXX0的策略，所以说XXXXX000是必胜的。
总体上可以这样理解 =_=

代码如下

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 用于记录当前状态是否被搜索过
unordered_map<string, bool> m;
bool check(string s) {
    return count(s.begin(), s.end(), '0') == 1;
}
bool dfs(string s) {
    if (m.count(s))
        return m[s];
    if (check(s))
        return m[s] = false;
    // 模拟下一步是一颗棋子
    for (int i = 0; i < 8; ++i) {
        if (s[i] == '0') {
            string tmp = s;
            tmp[i] = 'X';
            // 如果下一步是必败的，那么我们这步必胜
            if (!dfs(tmp)) 
                return m[s] = 1;
        }
    }
    // 模拟下一步是二颗棋子
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            int k = i * 4 + j;
            if (s[k] == '0' && s[k + 1] == '0') {
                string tmp = s;
                tmp[k] = tmp[k + 1] = 'X';
                if (!dfs(tmp)) 
                    return m[s] = 1;
            }
        }
    }
    // 运行到此，这说明不存在下一步是必败的情况，所有我们这一步输了
    return m[s] = false;
}
int main() {
    string s[4] = {"X0000000", "XX000000", "0X000000", "0XX00000"};
    for (auto i: s) {
        cout << (dfs(i)? 'L': 'V');
    }
    return 0;
}