• 蓝桥杯 灭鼠先锋 博弈


    问题描述

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

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

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

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

    1. XOOO XXOO OXOO OXXO
    2. OOOO OOOO OOOO OOOO

    其中 O 表示棋盘上的一个方格为空,X 表示该方格已经放置了棋子。

    请问,对于以上四种情况,如果小蓝和小乔都是按照对自己最优的策略来玩游戏,小蓝是否能获胜。如果获胜,请用 V 表示,否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。

    运行限制

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

    总通过次数: 153  |  总提交次数: 166  |  通过率: 92.2%

    难度: 简单   标签: 省赛, 2022

    精选项目课程_IT热门课程_蓝桥云课课程 - 蓝桥云课

    ===================================================

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

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

    此外需要注意该题

    1. import java.util.HashMap;
    2. import java.util.Map;
    3. // 1:无需package
    4. // 2: 类名必须Main, 不可修改
    5. public class Main {
    6. public static Map SG = new HashMap<>();
    7. public static void main(String[] args) {
    8. String[] s = new String[]{"XOOOOOOO", "XXOOOOOO", "OXOOOOOO", "OXXOOOOO"};
    9. StringBuilder sb = new StringBuilder();
    10. int n = s.length;
    11. for (int i = 0; i < n; i++) {
    12. if (put(s[i])) sb.append("L");
    13. else sb.append("V");
    14. }
    15. System.out.println(sb);
    16. }
    17. public static boolean check(String s) {
    18. int count = 0;
    19. char[] cs = s.toCharArray();
    20. int n = cs.length;
    21. for (int i = 0; i < n && count <= 1; i++) {
    22. if (cs[i] == 'O') count++;
    23. }
    24. return count == 1;
    25. }
    26. public static boolean put(String s) {
    27. if (SG.containsKey(s)) return SG.get(s);
    28. if (check(s)) {
    29. SG.put(s, false);
    30. return false;
    31. }
    32. char[] cs = s.toCharArray();
    33. int n = cs.length;
    34. // 放一个
    35. for (int i = 0; i < n; i++) {
    36. if (cs[i] == 'O') {
    37. StringBuilder sb = new StringBuilder(s);
    38. sb.replace(i, i + 1, "X");
    39. // 可以转移为必败态 必为必胜
    40. if (!put(sb.toString())) {
    41. SG.put(s, true);
    42. return true;
    43. }
    44. }
    45. }
    46. // 放两个连续的
    47. for (int i = 0; i < n - 1; i++) {
    48. if (cs[i] == 'O' && cs[i + 1] == 'O' && i != 3) {
    49. StringBuilder sb = new StringBuilder(s);
    50. sb.replace(i, i + 2, "XX");
    51. if (!put(sb.toString())) {
    52. SG.put(s, true);
    53. return true;
    54. }
    55. }
    56. }
    57. // 不能转移到必败态,所以自己必败
    58. SG.put(s, false);
    59. return false;
    60. }
    61. }

  • 相关阅读:
    Xml转json
    04_面向对象高级_final与常量
    Linux基本常用命令大全(附案例实战)
    Makefile 精要(用得最多的规则-附示例)
    tensorflow笔记
    在阿里做前端程序员,我是这样规划的
    4个高质量站点推荐值得收藏
    Shell之基础概念和变量
    T1082 求小数的某一位 (信息学一本通C++)
    DSPE-PEG-TH,TH-PEG-DSPE,磷脂-聚乙二醇-靶向肽TH
  • 原文地址:https://blog.csdn.net/weixin_45322373/article/details/127698091