当前位置：首页 > news >正文

华为OD机试真题---开心消消乐

news 2024/11/29 5:29:15

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

一、题目描述

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

当点击一个1时，该1被反转为0，同时相邻的上、下、左、右，以及左上、左下、右上、右下8个方向的1（如果存在）均会自动反转为0。
进一步地，一个位置上的1被反转为0时，与其相邻的8个方向的1（如果存在）均会自动反转为0。

请问，给定一个矩阵，最少需要点击几次后，所有数字均为0？

输入：

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

输出：

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

二、解题思路

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

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

三、代码实现

import java.util.Scanner;public class HappyElimination {// 定义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);}}// 主方法，用于计算最少点击次数public static int happyElimination(int[][] matrix) {// 初始化点击次数为0int 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;}/*** 主函数入口* 该函数用于读取用户输入的矩阵，并计算通过“开心消除”游戏后的矩阵得分* @param args 命令行参数，未使用*/public static void main(String[] args) {// 创建Scanner对象以读取用户输入Scanner scanner = new Scanner(System.in);// 读取矩阵的行数和列数int N = scanner.nextInt();int M = scanner.nextInt();// 读取矩阵的初始值int[][] matrix = new int[N][M];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {matrix[i][j] = scanner.nextInt();}}// 调用方法并输出结果int result = happyElimination(matrix);System.out.println(result);// 关闭Scanner对象scanner.close();}
}

四、示例解析

输入：

输出：

解析：

初始矩阵为：

第一次点击左上角的1，消除其及其相邻的8个方向的1，得到：

第二次点击右下角的1（注意，此时它已经是唯一的1了），消除它，得到全0矩阵：

因此，最少需要点击2次后，所有数字均为0。

为了更直观的看懂实现，看如下解析：

运行示例解析

输入：

解析：

读取输入：
- 首先，程序读取了两个整数4和4，分别表示矩阵的行数N和列数M。
- 接着，程序读取了一个4x4的矩阵，其初始值为：
```
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
```
初始化：
- 程序创建了一个与输入矩阵大小相同的布尔矩阵visited，用于记录每个位置是否已被访问过。初始时，所有位置都未被访问，因此visited矩阵的所有元素都初始化为false。
- 点击次数clickCount被初始化为0。
遍历矩阵：
- 程序开始遍历整个矩阵，寻找值为1且未被访问过的位置。
深度优先搜索（DFS）：
- 当程序找到第一个值为1且未被访问过的位置（例如，左上角的位置(0, 0)）时，它调用dfs方法从该位置开始进行深度优先搜索。
- dfs方法会将当前位置标记为已访问，并将其值设为0。然后，它会对当前位置的8个相邻方向进行递归搜索，并将所有相连的1都标记为0和已访问。
- 在这个例子中，从(0, 0)位置开始的DFS搜索会消除左上角的整个连续1区域，包括(0, 0), (0, 1), (1, 0), (1, 1)这四个位置。
- DFS完成后，点击次数clickCount增加1。
继续遍历：
- 程序继续遍历矩阵，寻找下一个值为1且未被访问过的位置。在这个例子中，下一个这样的位置是右下角的(3, 3)。
- 从(3, 3)位置开始的DFS搜索会消除右下角的整个连续1区域。
- DFS完成后，点击次数clickCount再次增加1。
结束遍历：
- 此时，矩阵中所有的1都已被消除，且没有更多的1可供搜索。程序结束遍历。
输出结果：
- 程序输出点击次数clickCount的值，即2。