深圳做网站建设开发,数据库网页制作教程,装修在线设计平台,银川做网站的公司给定一个 N 行 M 列的二维矩阵#xff0c;矩阵中每个位置的数字取值为 0 或 1#xff0c;矩阵示例如#xff1a;
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0#xff0c;规则如下#xff1a;
当点击一个 1 时#xff0c;该 1 被反转为 0矩阵中每个位置的数字取值为 0 或 1矩阵示例如
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0规则如下
当点击一个 1 时该 1 被反转为 0同时相邻的上、下、左、右以及左上、左下、右上、右下 8 个方向的 1 如果存在 1均会自动反转为 0进一步地一个位置上的 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 11 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 i0;iarr.length;i){for(int j0;jarr[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 (row0||col0||rowarr.length-1||colarr[0].length-1){return;}//如果某个位置值为 1if (arr[row][col] 1){//置为0arr[row][col] 0;//左dfs(arr,row-1,col);//右dfs(arr,row1,col);//上dfs(arr,row,col-1);//下dfs(arr,row,col1);//右下dfs(arr,row1,col1);//左上dfs(arr,row-1,col-1);//右上dfs(arr,row1,col-1);//左下dfs(arr,row-1,col1);}}
