Mine

时间限制： 1 秒

空间限制： 512 MB

相关文件： 题目目录

题目描述

扫雷（minesweeper）是一个有趣的单人益智类游戏，游戏目标是在最短的时间内根据棋盘上的提示信息，找出所有非雷方块，同时避免踩到地雷。随着桌面操作系统Windows的流行，其自带的扫雷游戏也因为有趣的玩法、精致的画面受到大家的欢迎。

小L的电脑上曾经也有一个扫雷游戏，它和主流的扫雷游戏基本相似，但是有一些不同的地方，具体介绍如下：

游戏开始时，玩家可以看到 \(N\times M\) 个整齐排列的空白方块，玩家须根据棋盘已有的信息，运用逻辑推理来推断哪些方块含或不含地雷。

玩家可以用鼠标左键点击空白方块，表示推断这个方块没有地雷，尝试探明它。

如果玩家点开没有地雷的方块，会有一个数字显现其上，这个数字代表着八连通的相邻方块有多少颗地雷（至多为 \(8\)）

如果这个方块八连通的方块中没有地雷（也即，方块显示的数字为 \(0\)），则系统会自动帮玩家点开它相邻的方块，这个过程可能会引起连锁反应。

如果玩家点开有地雷的方块，则游戏结束，玩家失败。

玩家可在推测有地雷的方块上点鼠标右键，表示放置旗帜来标明地雷的位置；在有旗帜的方块上再次点击右键，会使旗帜消失，成为空白的方块。在已标明旗帜的方块点击左键，方块不会有任何的变动。若在游戏进行中错置旗帜，可以用右键来改变方块状态。

玩家可以在一个已探明的方块上同时点击左键及右键。此时，如果方块相邻的 \(8\) 个方块放置旗帜的数目与方块上的数字相同，那么周围未探明的方块就会自动打开。然而，玩家若错置旗帜位置，此动作可能会打开真正藏有地雷的方块，导致游戏失败。不过这样的点击动作可加快游戏速度以便得到高分。

然而，年代久远，小 L 已经找不到当年陪他度过十年求学时光的扫雷游戏了，于是他找到了精通编程的你，希望你能帮他写一个简单的扫雷游戏，帮助他回忆那些快乐时光。

具体来说，你的程序应该读入一个地雷布置图。然后读入用户的每一次游戏操作，并在每次操作后给用户以反馈，帮助用户进行游戏。

输入格式

从标准输入读入数据。

约定：我们用坐标 \((x, y)\) 表示棋盘第 \(x\) 行、第 \(y\) 列的方块。

第一行用空格隔开的两个整数 \(n,m\)，表示棋盘的规模。

接下来 \(n\) 行，每行一个长为 \(m\) 的字符串，描述棋盘，其中第 \(i\) 行的第 \(j\) 个字符表示棋盘的方块 \((i, j)\)。为 * 表示方块里有一个地雷，为 . 表示方块是安全的。

接下来每一行按时间顺序描述每一次用户操作，直到文件结束。每一行的格式如下：

首先读入一个字符串，表示这次操作的内容：
Flag：表示右键点击某个方块，插上／撤销一面旗帜。
Sweep：表示左键点击某个方块，判断这个方块没有地雷，要探明之。
DSweep：表示左右键同时点击某个方块，尝试探明与它相邻的方块。
Quit：表示放弃本局游戏并退出。
若操作不为 Quit，则之后有空格隔开的两个整数 \(x,y\)，表示这次操作的坐标为 \((x, y)\)，保证 \(1\leq x\leq n\), \(1\leq y\leq m\)。

输入数据保证存在有且仅有一次 Quit 操作。

输出格式

输出到标准输出。

对每一次操作，向标准输出打印一行或多行，表示此次操作的反馈。具体格式如下：

若读入了 Quit，忽略之后的所有输入，结束本局游戏，输出结束信息（见第 \(8\) 条）。
对 Flag 操作：
如果对应方块已经被探明，输出一行 swept。
如果对应方块未被探明，插上旗帜，输出一行 success。
如果对应方块上有旗帜，清除之，输出一行 cancelled。
对 Sweep 操作：
如果对应方块已经被探明，输出一行 swept。
如果对应方块上有旗帜，输出一行 flagged。
如果对应方块未被探明，进行扫雷过程，根据扫雷的结果，输出反馈信息（见第 \(5、6\) 条）。
对 DSweep 操作：
如果对应方块未被探明，输出一行 not swept。
如果对应方块数字为 \(0\)、或者它八连通的方块的旗帜数不等于方块显示的数，输出一行 failed。
否则，对方块八连通的每个空白方块进行扫雷过程，所有扫雷过程结束之后，根据扫雷的结果，输出反馈信息（见第 \(6、7\) 条）。
扫雷过程，假设要对 \((x, y)\) 进行扫雷：
如果 \((x,y)\) 为地雷，扫雷失败。输出一行 boom。接着，忽略之后的所有输入，结束本局游戏，输出结束信息（见第 \(8\) 条）。
否则，标记这个方块为“已探明”，令这个方块显示它相邻的方块的地雷总数。如果它相邻的方块不存在地雷，则自动对它相邻的没有探明的方块进行扫雷（此时，清除它的相邻方块上的旗帜信息），这个过程可能会引起连锁反应。
对 Sweep 操作，在扫雷过程成功结束之后输出扫雷反馈；对 DSweep 操作，在所有的扫雷过程（可能是 \(0\) 次）成功结束之后输出扫雷反馈，格式如下：
如果没有任何新方块被探明（可能在 DSweep 时发生），输出一行：no cell detected。
否则，设有 \(num\_of\_cells\) 个新方块被探明，首先输出一行：NUM_OF_CELLS cell(s) detected，其中 NUM_OF_CELLS 应该输出本次操作探明的方块数，请注意括号的输出。
接下来 \(num\_of\_cells\) 行，将所有新探明的方块按照所在行为第一关键字，所在列为第二关键字，从小到大排序输出，每一行输出空格隔开的三个整数 \(x,y,c\)，其中 \(x, y\) 表示方块的坐标，\(c\) 表示方块上显示的数字。
若某次 Sweep / DSweep 操作结束之后，所有没有地雷的方块均被探明，忽略之后的所有输入，结束本局游戏，输出结束信息（见第 \(8\) 条）。
结束信息的输出格式：
首先，输出游戏胜负情况：
若所有没有地雷的方块均被探明，输出一行：finish；
若踩到雷而结束游戏，输出一行：game over；
若因为 Quit 而结束游戏，输出一行：give up。
之后，计算玩家使用的行动次数 \(total\_step\)，每次成功／不成功的 Flag, Sweep, DSweep 均视为一次行动，Quit 不算一次行动，输出一行：total step TOTAL_STEP，其中 TOTAL_STEP 应该输出行动次数。

注意：请特别注意各项输出的拼写和空格，否则将可能导致程序错误直至零分。

样例1输入

3 3
...
..*
...
Sweep 1 1
DSweep 1 2
Flag 1 3
Flag 2 3
DSweep 1 2
Sweep 1 3
Flag 1 1
DSweep 1 3
Flag 1 3
DSweep 1 2
DSweep 1 2
Sweep 3 3
Quit

样例1输出

6 cell(s) detected
1 1 0
1 2 1
2 1 0
2 2 1
3 1 0
3 2 1
failed
success
success
failed
flagged
swept
not swept
cancelled
1 cell(s) detected
1 3 1
no cell detected
1 cell(s) detected
3 3 1
finish
total step 12

样例1解释

第一组数据展示了一个在简单的 \(3\times 3\) 棋盘上进行的游戏过程，样例输出中展示了上文提到的绝大部分输出信息。

样例2

见题目目录下的 2.in 与 2.ans。

样例2解释

第二组数据展示了一种因为错误的 Flag 操作和 DSweep 操作而导致游戏失败的情况。

样例3

见题目目录下的 3.in 与 3.ans。

样例3解释

第三组数据展示了一种因为 Quit 操作而结束游戏的情况，注意，当游戏结束之后，你的程序应该输出结束信息，并忽略之后的所有操作。

子任务

共有 \(20\) 个测试点，每个测试点满分为 \(5\) 分。

我们令 \(n,m\) 表示棋盘的规模，\(q\) 表示输入的操作次数，有以下约定：

测试点	\(n\)	\(m\)	\(q\)	性质
\(1\) ~ \(2\)	\(\leq 10\)	\(\leq 10\)	\(\leq 60\)	A
\(3\) ~ \(4\)	\(\leq 10\)	\(\leq 10\)	\(\leq 60\)	B
\(5\) ~ \(6\)	\(\leq 10\)	\(\leq 10\)	\(\leq 60\)	无
\(7\) ~ \(8\)	\(=1\)	\(\leq 1000\)	\(\leq 1000\)	A
\(9\) ~ \(10\)	\(=1\)	\(\leq 1000\)	\(\leq 1000\)	B
\(11\) ~ \(12\)	\(=1\)	\(\leq 1000\)	\(\leq 1000\)	无
\(13\) ~ \(14\)	\(\leq 300\)	\(\leq 300\)	\(\leq 8000\)	A
\(15\) ~ \(16\)	\(\leq 300\)	\(\leq 300\)	\(\leq 8000\)	B
\(17\) ~ \(19\)	\(\leq 300\)	\(\leq 300\)	\(\leq 8000\)	无
\(20\)	\(\leq 1000\)	\(\leq 1000\)	\(\leq 60000\)	无

性质A：保证只有 Sweep 操作和 Quit 操作。

性质B：保证没有 DSweep 操作。

注意：对于规模较大的数据，请不要使用过于缓慢的输出方式。