首页 > 试题广场 >

大家来扫雷

[编程题]大家来扫雷

热度指数：1559 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小M最近爱上了扫雷游戏，就是在一个n*m的区域中，有地雷，每一个方格上都有一个数字s，表示在这个方格周围有s颗雷，现在给你一张表明地雷的图，并且指定一个位置点开，请输出点开后的数字情况，若点开的地方的数字为0，则向该方格周围扩展，直到遇到数字或者地图边界为止，若点开的地方为地雷,那么直接输出"GG"。

周围指的是上，左上，左，左下，下，右下，右，右上八个方向。

输入描述:

第一行有两个数字n和m(2<=n,m<=1000)，表示地图的大小，第二行有两个整数x和y(1<=x<=n,1<=y<=m)，表示点击第x行y列的方格，接下来的是一个n行m列的一个矩阵，表示地图，其中.表示空地，*表示地雷。

输出描述:

如果点开的地方为地雷直接输出"GG"。否则输出点击指定位置后的地图，"."表示未点开的空地，"*"表示地雷，数字表示在该方格周围的地雷数目。

示例1

输入

3 4
1 1
....
..*.
....

输出

01..
01*.
01..

算法知识视频讲解

牛客题解官

发表于 2020-06-05 18:57:28

题解：考察点：搜索题解：如果最开始位置是炸弹，则不存在可扩展的可能性，一定输出。否则其他情况一定是可以扩展的。采用广度优先搜索进行坐标的扩展。对于一个位置，对其周围个方向进行遍历，如果有越界，或者不能扩展的位置，则剪掉；如果周围个方向存在数字为的，则将其加入队列，作为新的进行新一轮的扩展，直展开全文