首页 > 代码库 > mine layer(2008 World Final C)

mine layer(2008 World Final C)

类似于扫雷游戏,在一些格子中散步着一些地雷,具体的埋藏位置并不清楚,但知道每个格子及其周围八个格子的地雷总数。请问此时正中间哪一行最多可能有多少地雷(题目假定所有的输入都是奇数行的)?

限制条件

输入有R行C列

small

R=3,5

3≤C≤5

Large

3≤R≤49,R是奇数

3≤C≤49

样例1

输入

R=3,C=3

2 2 1

3 4 3

2 3 2

输出

1(地雷的分布只有右图一种)

样例2

输入

 R=3,C=3

各个格子的信息如下

2 2 1

3 4 3

2 3 2

输出

1(对应题目描述中的例图)

 

分析:

本题从简单情况开始考虑。

一维的情况:

每个格子内有一个数字,但具体数字不详。但知道该格子和左右两个相邻的格子内的数字之和。

  一维格子中的数字之和:4 8 9 8 6 6 5

  一维格子中的数字:      2 2 4 3 1 2 3

 按模3的余数分类讨论: