华为OD机试真题【开心消消乐】

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);  // 向左}