11.华为OD机试真题—开心消消乐

华为OD机试真题“开心消消乐”是一道有趣的算法题，主要考察的是对二维矩阵的遍历和深度优先搜索（DFS）算法的应用。以下是对这道题的详细解析：

一、题目描述

给定一个N行M列的二维矩阵，矩阵中每个位置的数字取值为0或1。现需要将矩阵中所有的1进行反转为0，规则如下：

1.当点击一个1时，该1被反转为0，同时相邻的上、下、左、右，以及左上、左下、右上、右下8个方向的1（如果存在）均会自动反转为0。
2.进一步地，一个位置上的1被反转为0时，与其相邻的8个方向的1（如果存在）均会自动反转为0。
请问，给定一个矩阵，最少需要点击几次后，所有数字均为0？

输入：

第一行输入两个整数，分别表示矩阵的行数N和列数M，取值范围均为[1,100]。
接下来N行表示矩阵的初始值，每行均为M个数，取值范围[0,1]。

输出：

输出一个整数，表示最少需要点击的次数。

二、解题思路

这个问题可以看作是一个图搜索问题，其中矩阵中的1表示图中的节点，相邻的1之间通过边相连。我们的目标是通过最少的点击次数（即最少的步数）来遍历并消除所有的1。

1.遍历矩阵：首先，我们需要遍历整个矩阵，找到所有的1。
2.深度优先搜索（DFS）：对于每一个找到的1，我们使用DFS来搜索并消除与其相连的所有1。在DFS的过程中，我们需要标记已经访问过的节点（即将1变为0），以避免重复访问。
3.统计点击次数：每当我们从一个未访问过的1开始进行DFS搜索时，就意味着我们需要进行一次点击。因此，我们可以使用一个计数器来统计点击的次数。

三、代码实现

package com.study.algorithm.huaweiOrOD.huaweiOD202509082334.华为OD机试真题开心消消乐;
 
import java.util.Scanner;
 
/**
 * @ProjectName: algorithm
 * @ClassName: HappyElimination
 * @Description: 华为OD机试真题---开心消消乐
 * @Author: Tony_Yi
 * @Date: 2025/11/27 23:35
 * @Version 1.0
 **/
public class HappyElimination {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] matrix = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int result = happyElimination(matrix);
        System.out.println(result);
        sc.close();
    }
 
    // 主方法，用于计算最少点击次数
    public static int happyElimination(int[][] matrix) {
        // 初始化点击次数为0
        int clickCount = 0;
        // 用于记录是否访问过某个位置
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        // 遍历整个矩阵
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                // 如果当前位置是1且未被访问过
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    // 从当前1开始进行DFS搜索
                    dfs(matrix, visited, i, j);
                    // 增加点击次数
                    clickCount++;
                }
            }
        }
        // 返回总的点击次数
        return clickCount;
    }
 
    // 定义DFS方法，用于消除与给定坐标相连的所有1
    /**
     * 使用深度优先搜索算法遍历并修改矩阵中与指定坐标(x, y)相连的所有1为0。
     * 此方法主要用于在二维矩阵中寻找并消除连续的1。
     *
     * @param matrix 二维整数数组，表示待处理的矩阵。
     * @param visited 二维布尔数组，表示矩阵中各位置的访问状态。
     * @param x 指定坐标的x轴值，表示从该位置开始处理。
     * @param y 指定坐标的y轴值，表示从该位置开始处理。
     */
    private static void dfs(int[][] matrix, boolean[][] visited, int x, int y) {
        /**
         * 检查边界条件和是否已经访问过
         * 如果当前位置(x, y)超出矩阵边界，或者当前位置不是1，或者已经访问过，则直接返回。
         * 这是为了避免数组越界和重复访问。
         */
        if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length || matrix[x][y] != 1 || visited[x][y]) {
            return;
        }
 
        // 标记当前节点为已访问
        /**
         * 将当前位置标记为已访问，并将其值设为0，表示已经处理过。
         */
        visited[x][y] = true;
        matrix[x][y] = 0; // 将1变为0
 
        // 定义8个相邻方向的偏移量
        /**
         * 定义dx和dy数组来表示8个相邻方向的偏移量，以便后续对这些方向进行搜索。
         */
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
 
        // 对8个相邻方向进行DFS搜索
        /**
         * 遍历8个相邻方向，对每个方向递归调用DFS方法。
         * 通过这种方式，可以找到所有与当前位置相连的1，并将它们设为0。
         */
        for (int i = 0; i < 8; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            dfs(matrix, visited, newX, newY);
        }
    }
}