2505: 开心消消乐

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

给定一个N行M列的二维矩阵,矩阵中每个位置的数字取值为0或1。矩阵示例如: 1100 0001 0011 1111 现需要将矩阵中所有的1进行反转为0,规则如下: 1) 当点击一个1时,该1便被反转为0,同时相邻的上、下、左、右,以及左上、左下、右上、右下8 个方向的1(如果存在1)均会自动反转为0; 2)进一步地,一个位置上的1被反转为0时,与其相邻的8个方向的1(如果存在1)均会自动反转为0; 按照上述规则示例中的矩阵只最少需要点击2次后,所有值均为0。请问,给定一个矩阵,最少需要点击几次后,所有数字均为0?

Input

第一行为两个整数N和M,分别代表矩阵的行数和列数。 接下来的N行为矩阵的初始值,每行M个整数

Output

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

Sample Input Copy

3 3
1 0 1
0 1 0
1 0 1

Sample Output Copy

1

Source/Category