这个题目恰好用到前不久洛谷集训营第一天比赛的某个题目的std所用的方法. 正好我对那个方法不熟悉, 借这次机会好好学习下.

题目描述

扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。

现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。

注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

输入输出格式

输入格式:

输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。

接下来n行,每行m个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。

输出格式:

输出文件包含n行,每行m个字符,描述整个雷区。用’*’表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

输入输出样例

输入样例#1:

3 3
*??
???
?*?

输出样例#1:

*10
221
1*1

输入样例#2:

2 3
?*?
*??

输出样例#2:

2*1
*21

说明

对于 100%的数据, 1≤n≤100, 1≤m≤100。

From Luogu

这道题目思路很简单, 只需要遍历每个非雷处, 然后判断8个位置上的雷数并赋值到数组上即可. 但之所以想写这道题的题解原因就在这其中判断的方法. 在之前集训营我所遇到类似的题目, 我是通过写了4个大特判通过的. 足足写了几十行(因为要考虑数组边缘是否越界的问题) 但这道题如果要写特判, 就得写8个以上了. 细细一想马上放弃这个做法(我太懒了 因此就翻回以前类似题目的zyl老师的std参考参考.  大概模仿了一下方法.

通过定义两个数组, 分别代表x和y(也就是两个维度) 里面存放着与某个点的相对位置 然后一遍循环, 再加一个特判即可搞定.

[cc lang=”c”]
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
[/cc]
dx和dy的[0]都是-1 即代表原点的左上一格. 随后分别代表着 上 右上 左….

[cc lang=”c”]
for(int i = 0;i < 8;i ++) { nx = x + dx[i]; ny = y + dy[i]; if(nx >= 0 && ny >= 0 && nx < n && ny < m && t[nx][ny] == '*') { ans ++; } }[/cc]

循环表示某个点的8个相对位置, 如果越界了就略过~ 很方便的方法, 适合用在数组里一些规则的变化等等. 现在一想以前都是一个个的写判断防止越界, 我tm是得有多蠢.
另外这个题很有意思的一点就是在测试数据上, 这道题一开始是用字符读入输出的, 炸了一大半. 改成字符串读入输出马上AC. 好奇心让我一直研究下去. 最终修改一番(通过加getchar()吃换行符等等) 9个点都ac了 就最后一个点wa. 很神秘. 下载了数据测试, 发现输出很乱. 试着就输出读入内容, 发现还带有好多空白和换行! 一直弄了两个多小时, 最终发现, 复制下载下来的文件里的数据测试, 结果是乱的. 但是如果是我自己重新输入的数据, 结果又是正确的. 偶尔一想, 这tm不会是换行符的问题吧. 改动下一测马上正确. 万恶的最后一个测试点的数据居然是在Windows里生成, 而前面的都是在Linux上生成. 所以会有所不一样(有什么不一样? 请看上一篇) 该说蠢还是蠢呢. 前不久才被这个坑了好久, 这么快又遭了. 不过也正是因为有对这方面有所研究并特意写了blog记录. 最后能想起这个问题并解决了也是一件好事. (从此做题字符读入就格外小心了
Categories: OIer

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

P3371 单源最短路径 (最短路4种算法总结)

经过一星期的努力,总算把图论最短路的4个算法弄懂(可能) 其中包括Di Read more…

OIer

P2935 最好的地方 BestSpot

这是即hdu2066后的第3题Floyd题目, 第二题因为过水而没什么 Read more…

OIer

hdu2066 一个人的旅行 (Floyd)

初学图论, 其实还是dp的知识( 因为学校算法课讲dp讲到了floyd Read more…