P2594 [ZJOI2009]染色游戏

    • 101通过
    • 220提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 博弈论 素数判断,质数,筛法 递推 各省省选 2009 浙江
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一共n × m 个硬币,摆成n × m 的长方形。dongdong 和xixi 玩一个游戏, 每次可以选择一个连通块,并把其中的硬币全部翻转,但是需要满足存在一个 硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正 上方),并且这个硬币是从反面向上翻成正面向上。dongdong 和xixi 轮流操作。 如果某一方无法操作,那么他(她) 就输了。dongdong 先进行第一步操作,假 设双方都采用最优策略。问dongdong 是否有必胜策略。

    输入输出格式

    输入格式:

    第一行一个数T,表示他们一共玩T 局游戏。接下来是T 组游戏描述。每 组游戏第一行两个数n;m,接下来n 行每行m 个字符,第i 行第j 个字符如 果是“H” 表示第i 行第j 列的硬币是正面向上,否则是反面向上。第i 行j 列 的左上方是指行不超过i 并且列不超过j 的区域。

    输出格式:

    对于每局游戏,输出一行。如果dongdong 存在必胜策略则输出“-_-”(不含 引号) 否则输出“=_=”(不含引号)。(注意输出的都是半角符号,即三个符号 ASCII 码分别为45,61,95)

    输入输出样例

    输入样例#1: 复制
    3
    2 3
    HHH
    HHH
    2 3
    HHH
    TTH
    2 1
    T
    H
    输出样例#1: 复制
    =_=
    -_-
    -_-

    说明

    对于40% 的数据,满足1 ≤ n;m ≤ 5。

    对于100% 的数据,满足1 ≤ n;m ≤ 100,1 ≤ T ≤ 50。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。