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

2023-10-16 07:44
文章标签 算法 华为 机考 od 开心 消消

本文主要是介绍华为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代码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;/*** 开心消消乐* * @since 2023.10.13* @version 0.2* @author Frank**/
public class HappyCollapse {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String line = sc.nextLine();String[] rc = line.split(" ");int row = Integer.parseInt(rc[0]);int column = Integer.parseInt(rc[1]);int[][] matrix = new int[row][column];for (int i = 0; i < row; i++) {line = sc.nextLine();String[] strColumnValue = line.split(" ");int[] number = new int[column];for (int j = 0; j < column; j++) {number[j] = Integer.parseInt(strColumnValue[j]);}matrix[i] = number;}processHappyCollapse(matrix, row, column);}}static class Node {int i;int j;public Node(int i, int j) {this.i = i;this.j = j;}@Overridepublic int hashCode() {return (i + " " + j).hashCode();}@Overridepublic boolean equals(Object obj) {if (!(obj instanceof Node))return false;Node node = (Node) obj;return node.i == i && node.j == j;}}private static void processHappyCollapse(int[][] matrix, int row, int column) {Set<Node> nodeSet = new HashSet<Node>();List<Node> nodeList = new ArrayList<Node>();for (int i = 0; i < row; i++) {for (int j = 0; j < column; j++) {if (matrix[i][j] == 1) {Node node = new Node(i, j);nodeList.add(node);nodeSet.add(node);}}}int[] rowColumn = new int[2];rowColumn[0] = row;rowColumn[1] = column;int minCnt = Integer.MAX_VALUE;for (int i = 0; i < nodeList.size(); i++) {List<Node> copyOfList = new ArrayList<Node>();copyOfList.addAll(nodeList);Set<Node> copyOfSet = new HashSet<Node>();copyOfSet.addAll(nodeSet);Node node = nodeList.get(i);copyOfList.remove(i);copyOfSet.remove(node);int cnt = startClickNode(node, copyOfList, copyOfSet, rowColumn);if (cnt < minCnt) {minCnt = cnt;}}System.out.println(minCnt);}private static int startClickNode(Node node, List<Node> nodeList, Set<Node> nodeSet, int[] rowColumn) {int clickCnt = 1;clickCollapseNode(node, nodeList, nodeSet, rowColumn);if (nodeList.size() == 0) {return 1;}int minCnt = Integer.MAX_VALUE;for (int i = 0; i < nodeList.size(); i++) {List<Node> copyOfList = new ArrayList<Node>();copyOfList.addAll(nodeList);Set<Node> copyOfSet = new HashSet<Node>();copyOfSet.addAll(nodeSet);Node curNode = nodeList.get(i);copyOfList.remove(i);copyOfSet.remove(curNode);int cnt = startClickNode(curNode, copyOfList, nodeSet, rowColumn);if (cnt < minCnt) {minCnt = cnt;}}return clickCnt + minCnt;}private static void clickCollapseNode(Node node, List<Node> nodeList, Set<Node> nodeSet, int[] rowColumn) {int row = rowColumn[0];int column = rowColumn[1];if (node.i >= 1) {colapseNode(new Node(node.i - 1, node.j), nodeList, nodeSet, rowColumn);}if (node.i < row - 1) {colapseNode(new Node(node.i + 1, node.j), nodeList, nodeSet, rowColumn);}if (node.j >= 1) {colapseNode(new Node(node.i, node.j - 1), nodeList, nodeSet, rowColumn);}if (node.j < column - 1) {colapseNode(new Node(node.i, node.j + 1), nodeList, nodeSet, rowColumn);}if (node.i >= 1 && node.j >= 1) {colapseNode(new Node(node.i - 1, node.j - 1), nodeList, nodeSet, rowColumn);}if (node.i >= 1 && node.j < column - 1) {colapseNode(new Node(node.i - 1, node.j + 1), nodeList, nodeSet, rowColumn);}if (node.i < row - 1 && node.j >= 1) {colapseNode(new Node(node.i + 1, node.j - 1), nodeList, nodeSet, rowColumn);}if (node.i < row - 1 && node.j < column - 1) {colapseNode(new Node(node.i - 1, node.j + 1), nodeList, nodeSet, rowColumn);}}private static void colapseNode(Node node, List<Node> nodeList, Set<Node> nodeSet, int[] rowColumn) {if (nodeSet.contains(node)) {nodeList.remove(node);nodeSet.remove(node);clickCollapseNode(node, nodeList, nodeSet, rowColumn);}}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var rowColumn = line.split(" ");var row = parseInt(rowColumn[0]);var column = parseInt(rowColumn[1]);var matrix = new Array();for (var i = 0; i < row; i++) {line = await readline();var strNumbers = line.split(" ");var numbers = new Array(column);for (var j = 0; j < column; j++) {numbers[j] = parseInt(strNumbers[j]);}matrix[i] = numbers;}processHappyCollapse(matrix, row, column);}
}();function processHappyCollapse(matrix, row, column) {var nodeSet = new Set();var nodeList = new Array();for (var i = 0; i < row; i++) {for (var j = 0; j < column; j++) {if (matrix[i][j] == 1) {var node = i + "," + j;nodeList.push(node);nodeSet.add(node);}}}var rowColumn = new Array();rowColumn[0] = row;rowColumn[1] = column;var minCnt = Number.MAX_VALUE;for (var i = 0; i < nodeList.length; i++) {var copyOfList = Array.from(nodeList);var copyOfSet = new Set(nodeSet);var node = nodeList[i];copyOfList.splice(i, 1);copyOfSet.delete(node);var cnt = startClickNode(node, copyOfList, copyOfSet, rowColumn);if (cnt < minCnt) {minCnt = cnt;}}console.log(minCnt);
}function startClickNode(node, nodeList, nodeSet, rowColumn) {var clickCnt = 1;clickCollapseNode(node, nodeList, nodeSet, rowColumn);if (nodeList.length == 0) {return 1;}var minCnt = Number.MAX_VALUE;for (var i = 0; i < nodeList.length; i++) {var copyOfList = Array.from(nodeList);var copyOfSet = new Set(nodeSet);var curNode = nodeList[i];copyOfList.splice(i, 1);copyOfSet.delete(curNode);var cnt = startClickNode(curNode, copyOfList, nodeSet, rowColumn);if (cnt < minCnt) {minCnt = cnt;}}return clickCnt + minCnt;
}function clickCollapseNode(node, nodeList, nodeSet, rowColumn) {var row = rowColumn[0];var column = rowColumn[1];var nodeStrValue = node.split(",");var nodeValue = new Array();nodeValue[0] = parseInt(nodeStrValue[0]);nodeValue[1] = parseInt(nodeStrValue[1]);for (var i = -1; i <= 1; i++) {if (nodeValue[0] + i < 0 || nodeValue[0] + i > row - 1) {continue;}for (var j = -1; j <= 1; j++) {if (i == 0 && j == 0) {continue;}if (nodeValue[1] + j < 0 || nodeValue[1] + j > column - 1) {continue;}colapseNode((nodeValue[0] + i) + "," + (nodeValue[1] + j), nodeList, nodeSet, rowColumn);}}}function colapseNode(node, nodeList, nodeSet, rowColumn) {if (nodeSet.has(node)) {var idx = nodeList.indexOf(node);nodeList.splice(idx, 1);nodeSet.delete(node);clickCollapseNode(node, nodeList, nodeSet, rowColumn);}
}

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

(完)

这篇关于华为OD机考算法题：开心消消乐的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/220066。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
最大公因数：欧几里得算法

最大公因数：欧几里得算法

简述         求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行 m=n，n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为：6 代码实现 #include<iostream>using namespace std;/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2