一个具体网站的seo优化,wordpress会员地址,医药包装设计公司,上海建设厅网站查询1、题目描述
【开心消消乐】 给定一个N行M列的二维矩阵#xff0c;矩阵中每个位置的数字取值为0或1。矩阵示例如#xff1a; 1100 0001 0011 1111 现需要将矩阵中所有的1进行反转为0#xff0c;规则如下#xff1a; 1#xff09; 当点击一个1时#xff0c;该1便被反转为…1、题目描述
【开心消消乐】 给定一个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
【输入描述】 第一行输入两个整数分别表示矩阵的行数 N 和列数 M取值范围均为 [1,100]。接下来 N 行表示矩阵的初始值每行均为 M 个数取值范围 [0,1]。
【输出描述】 输出一个整数表示最少需要点击的次数。 【实例一】 输入 3 3 1 0 1 0 1 0 1 0 1 输出 1说明上述样例中四个角上的1均在中间的1的相邻8个方向上因此只需要点击一次即可。
2、解题思路
此题与【岛屿数量】题类似可用dfs回溯遍历的方法感染矩阵的位置即将符合题意的方向的1都变成0统计需要多少次才能将矩阵中所有的值都变成0
3、参考代码
import java.util.Scanner;/*** Author * Date 2023/4/25 23:57*/
public class 开心消消乐 {public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNext()) {int n in.nextInt();int m in.nextInt();int[][] arr new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {arr[i][j] in.nextInt();}}int res 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (arr[i][j] 1) {infect(arr, i, j);res;}}}System.out.println(res);}}public static void infect(int[][] arr, int x, int y) {if(x 0 || y 0 || x arr.length || y arr[0].length || arr[x][y] ! 1) {return;}arr[x][y] 0; // 感染的过程infect(arr, x 1, y); // 向下infect(arr, x - 1, y); // 向上infect(arr, x, y 1); // 向右infect(arr, x, y - 1); // 向左infect(arr, x 1, y - 1); // 向左下infect(arr, x 1, y 1); // 向右上infect(arr, x 1, y 1); // 向右下infect(arr, x - 1, y 1); // 向左上}
}4、相似题目
1岛屿数量 区别在于这题指能向四个方向感染而【开心消消乐】能向八个方向感染
public int numIslands(char[][] grid) {int count 0;for(int i 0; i grid.length; i) {for(int j 0; j grid[0].length; j) {if(grid[i][j] 1){infect(grid, i, j);count;}}}return count;}private void infect(char[][] grid, int i, int j){if(i 0 || j 0 || i grid.length || j grid[0].length || grid[i][j] 0) return;grid[i][j] 0;infect(grid, i 1, j); // 向下infect(grid, i, j 1); // 向右infect(grid, i - 1, j); // 向上infect(grid, i, j - 1); // 向左}
