ZJUT-1488 ACM的另类扫雷!
原题:http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1488
Description:
大家一定都玩过扫雷这个游戏,打开游戏界面,左上角的数字表示地图中一共有多少雷,右面的数字表示所用的时间,下面的区域是扫雷区。现在,假设扫雷区已经被翻开一部分,那么数字就表示在与此方块相邻的 8 个方块中的雷数。
现在给出扫雷区域的高 n 宽 m ,以及地图中含有的雷数 k ,和已知部分。请计算这些雷的所有排布方式的数目。由于数目可能很大,所以只要输出 mod 10000 的结果既可。
Input:
有多组测试数据,执行到文件结束为止。每组数据的第一行为三个整数 n, m, k(0 < n, m <= 100, 0 < k <= 100),分别表示扫雷区域的高和宽,地图中含有的雷数。以下 n 行 每行 m 个字符 表示地图的具体情况。如果字符为 '0' 到 '8' 中的一个,则表示此区域已被探索,数字表示周围的雷数。如果为 '.' 则表示此区域未知。
Output:
对每组数据,输出地雷的所有排布方式的数目 mod 10000 后的结果。每组数据占一行。
Sample Input:
9 9 10
.10000000
110012321
00002....
00002....
00001....
00011....
1101.....
.101122..
1100001..
Sample Output:
24
----------------------------------------
想了很长时间,想不出来,不知道各位有什么好的算法。谢谢
希望能用 C++ 语言或者 C 语言实现。
[解决办法]
个人观点:
就跟平常扫雷一样
咱一般先从已经探测区域的边缘开始扫
比较容易
主要是对一些基本结构的雷分布的判定
先对输入的数据进行初始化,
初始化为二维数组
然后对于已经标记为0到8的区域进行探索
根据不同的情况判定某些区域肯定是地雷
对于剩下的区域以及雷数
进行全排列
就是可能的数目
[解决办法]
这里搜索雷只能搜索到边缘的部分吧?
比如
11001232100002....00002....
[解决办法]
我目前的思路是
先进行2个循环找未知区域...
找到未知区域判断周边8个位置是不是>0 && <=8 如果有0的话肯定代表这个位置不是地雷了吧
然后8个位置都>0 && <=8的话那么就对8个位置进行2次扫描判断周边哪些是已查询出来的区域
然后判断是否和这个位置的值相等
如果小于的话那么这个位置就算是地雷...