3503: 【DFS/BFS】2024E-开心消消乐

金币值:1 时间限制:2.000 s 内存限制:128 M
正确:227 提交:339 正确率:66.96% 命题人:

题目描述

给定一个 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]

输出格式

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

输入样例    复制

3 3
1 0 1
0 1 0
1 0 1

输出样例    复制

1