问题 F: 扫雷

问题 F: 扫雷

时间限制: 1 Sec  内存限制: 128 MB
提交: 171  解决: 39
[状态] [讨论版] [提交] [命题人:]
题目描述
《扫雷》是一款大众类的益智小游戏,于1992年发行。游戏目标是在最短的时间内根据点击格子出现的数字找出所有非雷格子,同时避免踩雷,踩到一个雷即全盘皆输。当某个位置为数字的时,代表它周围的八连通区域中有对应数量的雷。
kirai获取了简化版扫雷(没有标记雷的小旗)的后台数据(后台数据包括所有数字和雷的位置),转换为一个n*m(1≤n, m≤500)的矩阵并对格子类型做了如下标记:
雷被标记为'*';
点开的空白区域标记为'0';
未点开的空白区域标记为'.';
数字1~8代表周围有多少雷;
kirai非常笨,他希望你帮他完成这样的任务:
给定k(1≤k≤min(可扫位置数, 10))个位置坐标和扫雷游戏的后台数据,输出点开指定位置序列后游戏的结果,初始时游戏中没有点开任何位置。
注:数据保证扫雷过程中不会重复点击已扫位置。
输入
输入样例有多组,全部是正整数。首先输入样例组数T(T≤10)。
接下来输入T组数,每组数据第一行包括三个正整数n,m,k(1≤n, m≤500, 1≤k≤min(可扫位置数, 10))分别表示地图的行、列数和即将点开的位置数。紧接着是一个n*m的矩阵,代表扫雷的后台数据,。
矩阵后是k个整数对xi, yi(1≤i≤k, 1≤xi≤n, 1≤yi≤m),表示依次点开的位置。

输出
如果某一步踩到雷,输出"Game over in step x"(不包括引号",表示第x步踩中雷);未踩到雷则根据扫雷的游戏规则更新,并输出最后一步结束后显示给kirai的矩阵。
样例输入 Copy
1
5 5 3
2*11*
*2111
22...
*1...
11...
1 1
3 3
1 2
样例输出 Copy
Game over in step 3
提示
样例中每步后的情况:
2....
.....
.....
.....
.....

2..1.
.2111
.2000
.1000
.1000

Game over in step 3