题目解析和算法源码

华为OD机试 - 开心消消乐（Java & JS & Python & C & C++）_伏城之外的博客-CSDN博客

题目描述

给定一个 N 行 M 列的二维矩阵，矩阵中每个位置的数字取值为 0 或 1。矩阵示例如：

1 1 0 0

0 0 0 1

0 0 1 1

1 1 1 1

现需要将矩阵中所有的 1 进行反转为 0，规则如下：

1. 当点击一个 1 时，该 1 便被反转为0，同时相邻的上、下、左、右，以及左上、左下、右上、右下 8  个方向的 1（如果存在1）均会自动反转为 0
2. 进一步地，一个位置上的 1 被反转为0时，与其相邻的 8 个方向的 1（如果存在1）均会自动反转为0

按照上述规则示例中的矩阵只最少需要点击 2 次后，所有值均为 0。

请问，给定一个矩阵，最少需要点击几次后，所有数字均为 0？

输入描述

第一行为两个整数，分别表示句子的行数 N 和列数 M，取值范围均为 [1, 100]

接下来 N 行表示矩阵的初始值，每行均为 M 个数，取值范围 [0, 1]

输出描述

输出一个整数，表示最少需要点击的次数

用例1

输入

3 3
1 0 1
0 1 0
1 0 1

输出

1

说明

上述样例中，四个角上的 1 均在中间的 1 的相邻 8 个方向上，因此只需要点击一次即可

用例2

输入

4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

输出

2

说明

在上述 4 * 4 的矩阵中，只需要点击 2 次，即可将所有的 1 进行消除