P1971 [NOI2011]兔兔与蛋蛋游戏

    • 162通过
    • 333提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 二分图 最大匹配 深度优先搜索,DFS NOI系列 2011
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    夜已寂寞

    题目描述

    这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。 这个游戏是在一个n行m列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。 每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为:

    兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。

    蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空格。

    第一个不能按照规则操作的人输掉游戏。为了描述方便,下面将操作“将第x行第y列中的棋子移进空格中”记为M(x,y)。 例如下面是三个游戏的例子。

    最近兔兔总是输掉游戏,而且蛋蛋格外嚣张,于是兔兔想请她的好朋友——你——来帮助她。她带来了一局输给蛋蛋的游戏的实录,请你指出这一局游戏中所有她“犯错误”的地方。 注意:

    两个格子相邻当且仅当它们有一条公共边。

    兔兔的操作是“犯错误”的,当且仅当,在这次操作前兔兔有必胜策略,而这次操作后蛋蛋有必胜策略。

    输入输出格式

    输入格式:

    输入的第一行包含两个正整数 n、m。

    接下来 n行描述初始棋盘。其中第i 行包含 m个字符,每个字符都是大写英文字母"X"、大写英文字母"O"或点号"."之一,分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号"."恰好出现一次。

    接下来一行包含一个整数 k(1≤k≤1000) ,表示兔兔和蛋蛋各进行了k次操作。

    接下来 2k行描述一局游戏的过程。其中第 2i – 1行是兔兔的第 i 次操作(编号为i的操作) ,第2i行是蛋蛋的第i次操作。每个操作使用两个整数x,y来描述,表示将第x行第y列中的棋子移进空格中。

    输入保证整个棋盘中只有一个格子没有棋子, 游戏过程中兔兔和蛋蛋的每个操作都是合法的,且最后蛋蛋获胜。

    输出格式:

    输出文件的第一行包含一个整数r,表示兔兔犯错误的总次数。

    接下来r 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 i 行包含一个整数ai表示兔兔第i 个犯错误的操作是他在游戏中的第 ai次操作。

    1 ≤n≤ 40, 1 ≤m≤ 40

    输入输出样例

    输入样例#1: 复制
    1 6 
    XO.OXO 
    1 
    1 2 
    1 1 
    输出样例#1: 复制
    1
    1
    输入样例#2: 复制
    3 3 
    XOX 
    O.O 
    XOX 
    4 
    2 3 
    1 3 
    1 2 
    1 1 
    2 1 
    3 1 
    3 2 
    3 3 
    输出样例#2: 复制
    0
    输入样例#3: 复制
    4 4 
    OOXX 
    OXXO 
    OO.O 
    XXXO 
    2 
    3 2 
    2 2 
    1 2 
    1 3 
    输出样例#3: 复制
    2
    1
    2

    说明

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