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

不念不忘少年蓝@ 2023-10-09 19:53 17阅读 0赞

#### 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）[岛屿数量][Link 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);  // 向左
        }

[Link 1]: https://leetcode.cn/problems/number-of-islands/