开心消消乐

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

示例二

输入

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

输出

2

说明：第一个元素是1，点击后，右侧也是1，所以第一次点击紫色的1会置为0，当遍历到第二行最后一个元素时，发现该位置是1，则搜索它的周围位置，如果是1，置为0，然后继续搜索刚刚置为0的位置的周边位置，依次循环，则红色的1一次被置为0

1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

解题思路：遍历二维数组，遇到某个位置的值为1，则开始查找它周围8个方向的位置的值，如果是1，置为0。然后继续遍历下一个元素。使用DFS算法。

读取输入数据代码略，直接使用定义好的数组。

Java代码，以用例二为例

    public static void main(String[] args) {int[][] arr = {{1,1,0,0},{0,0,0,1},{0,0,1,1},{1,1,1,1}};int count = 0;for(int i=0;i<arr.length;i++){for(int j=0;j<arr[0].length;j++){if (arr[i][j] == 0){continue;}//遇到 1 开始搜索，计数加 1dfs(arr,i,j);count++;}}System.out.println(count);}private static void dfs(int[][] arr,int row,int col){//如果索引越界，退出if (row<0||col<0||row>arr.length-1||col>arr[0].length-1){return;}//如果某个位置值为 1if (arr[row][col] == 1){//置为0arr[row][col] = 0;//左dfs(arr,row-1,col);//右dfs(arr,row+1,col);//上dfs(arr,row,col-1);//下dfs(arr,row,col+1);//右下dfs(arr,row+1,col+1);//左上dfs(arr,row-1,col-1);//右上dfs(arr,row+1,col-1);//左下dfs(arr,row-1,col+1);}}