• 华为OD机考算法题：开心消消乐

    题目部分

    题目开心消消乐
    难度易
    题目说明给定一个 N 行 M 列的二维矩阵，矩阵中每个位置的数字取值为 0 或 1，矩阵示例如：
    1 1 0 0
    0 0 0 1
    0 0 1 1
    1 1 1 1
    现需要将矩阵中所有的 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]。
    输出描述输出一个整数，表示最少需要点击的次数。
    补充说明无
    ------------------------------------------------------
    示例
    示例1
    输入3 3
    1 0 1
    0 1 0
    1 0 1
    输出1
    说明上述样例中，四个角上的 1 均在中间的 1 的相邻 8 个方向上，因此只需要点击一次即可。
    示例2
    输入

    4 4
    1 1 0 0
    1 0 0 0
    0 0 0 1
    0 0 1 1 

    输出2
    说明在上述 4 * 4 的矩阵中，只需要点击 2 次（左上角 和 右下角），即可将所有的 1 消除。

    解读与分析

    题目解读：

    点击一个 1，它相邻八个方向的 1 变成 0，与此同时，这八个方向如果存在 1 变成 0，那么与它相邻的八个方向的 1 也会变成 0。

    有点像扫雷游戏。

    分析与思路：

    此题可以采用广度优先搜索或深度优先搜索，遍历所有点击的情况。然后根据所有点击情况，计算出最小的点击次数。

    时间复杂度为 O(n^{2})，空间复杂度为 O(n^{2})。

    与《华为OD机考算法题：机器人活动区域》有些类似。

    代码实现

    Java代码

    1. import java.util.ArrayList;
    2. import java.util.HashSet;
    3. import java.util.List;
    4. import java.util.Scanner;
    5. import java.util.Set;
    6.  
    7. /**
    8.  * 开心消消乐
    9.  * 
    10.  * @since 2023.10.13
    11.  * @version 0.2
    12.  * @author Frank
    13.  *
    14.  */
    15. public class HappyCollapse {
    16. 	public static void main(String[] args) {
    17. 		Scanner sc = new Scanner(System.in);
    18. 		while (sc.hasNext()) {
    19. 			String line = sc.nextLine();
    20. 			String[] rc = line.split(" ");
    21. 			int row = Integer.parseInt(rc[0]);
    22. 			int column = Integer.parseInt(rc[1]);
    23.  
    24. 			int[][] matrix = new int[row][column];
    25. 			for (int i = 0; i < row; i++) {
    26. 				line = sc.nextLine();
    27. 				String[] strColumnValue = line.split(" ");
    28. 				int[] number = new int[column];
    29. 				for (int j = 0; j < column; j++) {
    30. 					number[j] = Integer.parseInt(strColumnValue[j]);
    31. 				}
    32. 				matrix[i] = number;
    33. 			}
    34.  
    35. 			processHappyCollapse(matrix, row, column);
    36. 		}
    37.  
    38. 	}
    39.  
    40. 	static class Node {
    41. 		int i;
    42. 		int j;
    43.  
    44. 		public Node(int i, int j) {
    45. 			this.i = i;
    46. 			this.j = j;
    47. 		}
    48.  
    49. 		@Override
    50. 		public int hashCode() {
    51. 			return (i + " " + j).hashCode();
    52. 		}
    53.  
    54. 		@Override
    55. 		public boolean equals(Object obj) {
    56. 			if (!(obj instanceof Node))
    57. 				return false;
    58. 			Node node = (Node) obj;
    59. 			return node.i == i && node.j == j;
    60. 		}
    61. 	}
    62.  
    63. 	private static void processHappyCollapse(int[][] matrix, int row, int column) {
    64. 		Set nodeSet = new HashSet();
    65. 		List nodeList = new ArrayList();
    66. 		for (int i = 0; i < row; i++) {
    67. 			for (int j = 0; j < column; j++) {
    68. 				if (matrix[i][j] == 1) {
    69. 					Node node = new Node(i, j);
    70. 					nodeList.add(node);
    71.  
    72. 					nodeSet.add(node);
    73. 				}
    74. 			}
    75. 		}
    76.  
    77. 		int[] rowColumn = new int[2];
    78. 		rowColumn[0] = row;
    79. 		rowColumn[1] = column;
    80.  
    81. 		int minCnt = Integer.MAX_VALUE;
    82. 		for (int i = 0; i < nodeList.size(); i++) {
    83. 			List copyOfList = new ArrayList();
    84. 			copyOfList.addAll(nodeList);
    85.  
    86. 			Set copyOfSet = new HashSet();
    87. 			copyOfSet.addAll(nodeSet);
    88.  
    89. 			Node node = nodeList.get(i);
    90.  
    91. 			copyOfList.remove(i);
    92. 			copyOfSet.remove(node);
    93.  
    94. 			int cnt = startClickNode(node, copyOfList, copyOfSet, rowColumn);
    95. 			if (cnt < minCnt) {
    96. 				minCnt = cnt;
    97. 			}
    98. 		}
    99. 		System.out.println(minCnt);
    100.  
    101. 	}
    102.  
    103. 	private static int startClickNode(Node node, List nodeList, Set nodeSet, int[] rowColumn) {
    104. 		int clickCnt = 1;
    105. 		clickCollapseNode(node, nodeList, nodeSet, rowColumn);
    106.  
    107. 		if (nodeList.size() == 0) {
    108. 			return 1;
    109. 		}
    110.  
    111. 		int minCnt = Integer.MAX_VALUE;
    112. 		for (int i = 0; i < nodeList.size(); i++) {
    113. 			List copyOfList = new ArrayList();
    114. 			copyOfList.addAll(nodeList);
    115.  
    116. 			Set copyOfSet = new HashSet();
    117. 			copyOfSet.addAll(nodeSet);
    118.  
    119. 			Node curNode = nodeList.get(i);
    120.  
    121. 			copyOfList.remove(i);
    122. 			copyOfSet.remove(curNode);
    123.  
    124. 			int cnt = startClickNode(curNode, copyOfList, nodeSet, rowColumn);
    125. 			if (cnt < minCnt) {
    126. 				minCnt = cnt;
    127. 			}
    128.  
    129. 		}
    130. 		return clickCnt + minCnt;
    131. 	}
    132.  
    133. 	private static void clickCollapseNode(Node node, List nodeList, Set nodeSet, int[] rowColumn) {
    134. 		int row = rowColumn[0];
    135. 		int column = rowColumn[1];
    136.  
    137. 		if (node.i >= 1) {
    138. 			colapseNode(new Node(node.i - 1, node.j), nodeList, nodeSet, rowColumn);
    139. 		}
    140. 		if (node.i < row - 1) {
    141. 			colapseNode(new Node(node.i + 1, node.j), nodeList, nodeSet, rowColumn);
    142. 		}
    143. 		if (node.j >= 1) {
    144. 			colapseNode(new Node(node.i, node.j - 1), nodeList, nodeSet, rowColumn);
    145. 		}
    146. 		if (node.j < column - 1) {
    147. 			colapseNode(new Node(node.i, node.j + 1), nodeList, nodeSet, rowColumn);
    148. 		}
    149. 		if (node.i >= 1 && node.j >= 1) {
    150. 			colapseNode(new Node(node.i - 1, node.j - 1), nodeList, nodeSet, rowColumn);
    151. 		}
    152. 		if (node.i >= 1 && node.j < column - 1) {
    153. 			colapseNode(new Node(node.i - 1, node.j + 1), nodeList, nodeSet, rowColumn);
    154. 		}
    155. 		if (node.i < row - 1 && node.j >= 1) {
    156. 			colapseNode(new Node(node.i + 1, node.j - 1), nodeList, nodeSet, rowColumn);
    157. 		}
    158. 		if (node.i < row - 1 && node.j < column - 1) {
    159. 			colapseNode(new Node(node.i - 1, node.j + 1), nodeList, nodeSet, rowColumn);
    160. 		}
    161. 	}
    162.  
    163. 	private static void colapseNode(Node node, List nodeList, Set nodeSet, int[] rowColumn) {
    164. 		if (nodeSet.contains(node)) {
    165. 			nodeList.remove(node);
    166. 			nodeSet.remove(node);
    167. 			clickCollapseNode(node, nodeList, nodeSet, rowColumn);
    168. 		}
    169. 	}
    170.  
    171. }

    JavaScript代码

    1. const rl = require("readline").createInterface({ input: process.stdin });
    2. var iter = rl[Symbol.asyncIterator]();
    3. const readline = async () => (await iter.next()).value;
    4. void async function() {
    5.     while (line = await readline()) {
    6.         var rowColumn = line.split(" ");
    7.         var row = parseInt(rowColumn[0]);
    8.         var column = parseInt(rowColumn[1]);
    9.  
    10.         var matrix = new Array();
    11.         for (var i = 0; i < row; i++) {
    12.             line = await readline();
    13.             var strNumbers = line.split(" ");
    14.             var numbers = new Array(column);
    15.             for (var j = 0; j < column; j++) {
    16.                 numbers[j] = parseInt(strNumbers[j]);
    17.             }
    18.             matrix[i] = numbers;
    19.         }
    20.  
    21.         processHappyCollapse(matrix, row, column);
    22.     }
    23. }();
    24.  
    25. function processHappyCollapse(matrix, row, column) {
    26.     var nodeSet = new Set();
    27.     var nodeList = new Array();
    28.     for (var i = 0; i < row; i++) {
    29.         for (var j = 0; j < column; j++) {
    30.             if (matrix[i][j] == 1) {
    31.                 var node = i + "," + j;
    32.                 nodeList.push(node);
    33.                 nodeSet.add(node);
    34.             }
    35.         }
    36.     }
    37.  
    38.     var rowColumn = new Array();
    39.     rowColumn[0] = row;
    40.     rowColumn[1] = column;
    41.  
    42.     var minCnt = Number.MAX_VALUE;
    43.     for (var i = 0; i < nodeList.length; i++) {
    44.         var copyOfList = Array.from(nodeList);
    45.         var copyOfSet = new Set(nodeSet);
    46.  
    47.         var node = nodeList[i];
    48.  
    49.         copyOfList.splice(i, 1);
    50.         copyOfSet.delete(node);
    51.  
    52.         var cnt = startClickNode(node, copyOfList, copyOfSet, rowColumn);
    53.         if (cnt < minCnt) {
    54.             minCnt = cnt;
    55.         }
    56.     }
    57.     console.log(minCnt);
    58. }
    59.  
    60. function startClickNode(node, nodeList, nodeSet, rowColumn) {
    61.     var clickCnt = 1;
    62.     clickCollapseNode(node, nodeList, nodeSet, rowColumn);
    63.  
    64.     if (nodeList.length == 0) {
    65.         return 1;
    66.     }
    67.  
    68.     var minCnt = Number.MAX_VALUE;
    69.     for (var i = 0; i < nodeList.length; i++) {
    70.         var copyOfList = Array.from(nodeList);
    71.         var copyOfSet = new Set(nodeSet);
    72.  
    73.         var curNode = nodeList[i];
    74.  
    75.         copyOfList.splice(i, 1);
    76.         copyOfSet.delete(curNode);
    77.  
    78.         var cnt = startClickNode(curNode, copyOfList, nodeSet, rowColumn);
    79.         if (cnt < minCnt) {
    80.             minCnt = cnt;
    81.         }
    82.     }
    83.     return clickCnt + minCnt;
    84. }
    85.  
    86. function clickCollapseNode(node, nodeList, nodeSet, rowColumn) {
    87.     var row = rowColumn[0];
    88.     var column = rowColumn[1];
    89.  
    90.     var nodeStrValue = node.split(",");
    91.     var nodeValue = new Array();
    92.     nodeValue[0] = parseInt(nodeStrValue[0]);
    93.     nodeValue[1] = parseInt(nodeStrValue[1]);
    94.  
    95.     for (var i = -1; i <= 1; i++) {
    96.         if (nodeValue[0] + i < 0 || nodeValue[0] + i > row - 1) {
    97.             continue;
    98.         }
    99.         for (var j = -1; j <= 1; j++) {
    100.             if (i == 0 && j == 0) {
    101.                 continue;
    102.             }
    103.             if (nodeValue[1] + j < 0 || nodeValue[1] + j > column - 1) {
    104.                 continue;
    105.             }
    106.             colapseNode((nodeValue[0] + i) + "," + (nodeValue[1] + j), nodeList, nodeSet, rowColumn);
    107.         }
    108.     }
    109.  
    110. }
    111.  
    112. function colapseNode(node, nodeList, nodeSet, rowColumn) {
    113.     if (nodeSet.has(node)) {
    114.         var idx = nodeList.indexOf(node);
    115.         nodeList.splice(idx, 1);
    116.         nodeSet.delete(node);
    117.         clickCollapseNode(node, nodeList, nodeSet, rowColumn);
    118.     }
    119. }

    虽然此题的难度标记为“易”，实际编码量比较大。难度并不小，在短时间内写出代码并不是很容易。

    (完)

  • 相关阅读:
    2022中国工业视觉市场研究报告【免费下载】
    Flutter简单聊天界面布局及语音录制播放
    深入理解 Docker 核心原理：Namespace、Cgroups 和 Rootfs
    橘子学MQ之rocketmq
    Java开发学习----AOP通知获取数据（参数、返回值、异常）
    Python之并发编程(线程)
    使用 Apache Camel 和 Quarkus 的微服务（四）
    ARM系列之ARM多核指令WFE、WFI、SEV原理
    竞赛选题 深度学习卫星遥感图像检测与识别 -opencv python 目标检测
    什么是透传模块 本人用过数据透传模块也开发过透传模块
  • 原文地址：https://blog.csdn.net/ZiJinShi/article/details/133760638