【华为OD-E卷-开心消消乐 100分(python、java、c++、js、c)】
题目
给定一个 N 行 M 列的二维矩阵,矩阵中每个位置的数字取值为 0 或 1。矩阵示例如:
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0,规则如下:
当点击一个 1 时,该 1 便被反转为0,同时相邻的上、下、左、右,以及左上、左下、右上、右下 8 个方向的 1(如果存在1)均会自动反转为 0 进一步地,一个位置上的 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
用例二:
输入:
4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
输出:
2
python解法
- 解题思路:
- 题目描述类似于“计算二维矩阵中连通块的个数”。在一个二维矩阵中,每个元素可能是1或0,其中1表示某个区域的一部分,0表示空白区域。两个1如果在上下左右或对角线相邻,则被视为同一个连通块的一部分。
解题步骤:
使用深度优先搜索(DFS)方法遍历二维矩阵,将属于同一连通块的所有1置为0,避免重复计数。
遍历整个矩阵,如果找到一个1,则说明发现了一个新的连通块,点击次数(clicks)加1,并通过DFS将该连通块标记清空。
最后输出连通块的总数(clicks)。
# 输入矩阵的行数和列数
n, m = map(int, input().split())# 输入矩阵的元素
matrix = [list(map(int, input().split())) for _ in range(n)]# 定义DFS函数,用于深度优先搜索
def dfs(x, y):# 将当前点标记为已访问(置为0)matrix[x][y] = 0# 遍历当前位置的8个方向(上下左右+对角线)for offsetX, offsetY in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:newI, newJ = x + offsetX, y + offsetY# 判断新位置是否在矩阵范围内,且为未访问的'1'if 0 <= newI < n and 0 <= newJ < m and matrix[newI][newJ] == 1:dfs(newI, newJ)# 初始化连通块计数器
clicks = 0# 遍历整个矩阵
for i in range(n):for j in range(m):# 如果找到一个未访问的'1',开始DFSif matrix[i][j] == 1:dfs(i, j) # 深度优先搜索清理连通块clicks += 1 # 连通块数量+1# 输出连通块的数量
print(clicks)
java解法
- 解题思路
- 题目是计算二维矩阵中连通块的个数,其中连通块由值为1的元素组成,并且连通规则包括上下左右以及对角线八个方向。我们采用广度优先搜索(BFS)的方法来解决这个问题:
遍历整个矩阵,找到值为1且未被标记的元素,视为一个新的连通块,计数加1。
使用一个队列进行BFS,将该连通块中的所有元素标记为已访问,避免重复计数。
BFS时,从当前元素出发,检查八个方向上的相邻元素,若其值为1且未被标记,则将其加入队列,继续处理。
重复上述过程,直到遍历完整个矩阵,输出连通块的数量
import java.util.*;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);// 输入矩阵的行数和列数int rowCount = input.nextInt();int colCount = input.nextInt();// 初始化矩阵int[][] matrix = new int[rowCount][colCount];for (int i = 0; i < rowCount; i++) {for (int j = 0; j < colCount; j++) {matrix[i][j] = input.nextInt();}}// 调用计算连通块数量的函数并输出结果System.out.println(calculateClicks(matrix, rowCount, colCount));}// 计算连通块数量的函数public static int calculateClicks(int[][] matrix, int rowCount, int colCount) {// 标记矩阵,用于记录某个位置是否已访问boolean[][] marked = new boolean[rowCount][colCount];// 初始化连通块计数器int clickCount = 0;// 遍历矩阵的每个元素for (int i = 0; i < rowCount; i++) {for (int j = 0; j < colCount; j++) {// 如果当前元素是未访问的'1',视为新连通块if (matrix[i][j] == 1 && !marked[i][j]) {clickCount++;// 使用队列进行BFSQueue<int[]> queue = new LinkedList<>();queue.add(new int[]{i, j});marked[i][j] = true; // 标记为已访问// BFS遍历连通块中的所有元素while (!queue.isEmpty()) {int[] point = queue.poll(); // 取出队列头部的坐标int x = point[0];int y = point[1];// 遍历当前位置的八个方向for (int[] dir : new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}) {int newX = x + dir[0];int newY = y + dir[1];// 检查新坐标是否在矩阵范围内,且是未访问的'1'if (newX >= 0 && newX < rowCount && newY >= 0 && newY < colCount && matrix[newX][newY] == 1 && !marked[newX][newY]) {marked[newX][newY] = true; // 标记新坐标为已访问queue.add(new int[]{newX, newY}); // 将新坐标加入队列}}}}}}// 返回连通块的数量return clickCount;}
}
C++解法
- 解题思路
- 本题使用并查集(Union-Find Set)解决,目标是统计二维矩阵中连通块的数量。每个值为1的元素被视为连通块的一部分,两个1如果在八个方向相邻,则属于同一个连通块。
具体步骤:
并查集初始化:将矩阵中每个元素映射为一维数组中的一个节点,构建并查集,每个节点初始时自成一个集合。
矩阵遍历:
对于每个值为1的元素,检查其八个方向上的相邻元素。
如果相邻元素值为1,将当前元素和相邻元素合并到同一集合中。
如果当前元素为0,则直接减少集合计数。
计数连通块:并查集中最终剩余的集合数即为连通块的数量。
优势:
使用并查集,能够高效处理连通块合并操作。
每次union操作和find操作的时间复杂度接近 O(1)(通过路径压缩和按秩合并优化)。
#include <iostream>
#include <vector>using namespace std;// 并查集类
class UnionFindSet {
public:vector<int> fa; // 父节点数组int count; // 连通块计数// 构造函数,初始化并查集UnionFindSet(int n) {fa.resize(n); // 初始化父节点数组count = n; // 初始时每个节点自成一个集合for (int i = 0; i < n; i++) {fa[i] = i;}}// 查找操作,路径压缩优化int find(int x) {if (x != fa[x]) {fa[x] = find(fa[x]); // 将当前节点直接连接到根节点}return fa[x];}// 合并操作,按秩优化void unionSets(int x, int y) {int x_fa = find(x); // 找到x的根节点int y_fa = find(y); // 找到y的根节点if (x_fa != y_fa) { // 如果不在同一集合fa[y_fa] = x_fa; // 将y的根节点连接到x的根节点count--; // 连通块数量减少}}
};// 获取连通块数量的函数
int getResult(vector<vector<int>>& matrix, int n, int m) {UnionFindSet ufs(n * m); // 构造一个大小为n*m的并查集// 八个方向的偏移量vector<vector<int>> offsets = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};// 遍历矩阵中的每个元素for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果当前元素不是1,减少连通块计数并跳过if (matrix[i][j] != 1) {ufs.count--;continue;}// 遍历8个方向的相邻元素for (const auto& offset : offsets) {int newI = i + offset[0]; // 新位置的行坐标int newJ = j + offset[1]; // 新位置的列坐标// 检查新位置是否在矩阵范围内且为1if (newI >= 0 && newI < n && newJ >= 0 && newJ < m && matrix[newI][newJ] == 1) {ufs.unionSets(i * m + j, newI * m + newJ); // 合并当前节点和相邻节点}}}}return ufs.count; // 返回连通块的数量
}int main() {int n, m;cin >> n >> m;// 输入矩阵vector<vector<int>> matrix(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> matrix[i][j];}}// 计算连通块数量并输出cout << getResult(matrix, n, m) << endl;return 0;
}
C解法
更新中
JS解法
核心思路:
并查集初始化:
将二维矩阵中的每个元素映射到一维数组,构建一个并查集。
初始时,每个元素自成一个集合。
遍历矩阵:
对于矩阵中值为1的元素,检查其八个方向的相邻元素是否也是1。
如果是,将当前元素与相邻元素合并到同一集合。
如果当前元素值为0,则从连通块计数中减1。
返回结果:
遍历完成后,并查集中剩余的集合数量即为连通块的数量。
优点:
并查集通过路径压缩和按秩优化,使find和merge操作的时间复杂度接近 O(1)。
算法整体复杂度为 O(n * m),适合处理大规模矩阵。
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});let data = [];
let rows, cols;rl.on("line", (input) => {data.push(input);// 读取第一行,获取矩阵的行数和列数if (data.length === 1) {[rows, cols] = data[0].split(" ").map(Number);}// 读取完整矩阵后开始处理if (rows && data.length === rows + 1) {data.shift(); // 去掉第一行const grid = data.map((row) => row.split(" ")); // 解析矩阵console.log(minClicks(grid, rows, cols)); // 输出结果data = [];}
});// 主函数:计算连通块数量
function minClicks(grid, rows, cols) {const dsu = new DisjointSet(rows * cols); // 初始化并查集const directions = [[-1, -1], // 左上[-1, 0], // 上[-1, 1], // 右上[0, -1], // 左[0, 1], // 右[1, -1], // 左下[1, 0], // 下[1, 1], // 右下];// 遍历矩阵的每个元素for (let r = 0; r < rows; r++) {for (let c = 0; c < cols; c++) {// 如果当前元素不是1,则减少连通块计数并跳过if (grid[r][c] != "1") {dsu.count--;continue;}// 遍历当前元素的八个方向for (let [dr, dc] of directions) {const newRow = r + dr;const newCol = c + dc;// 检查新位置是否在矩阵范围内且值为1if (newRow >= 0 &&newRow < rows &&newCol >= 0 &&newCol < cols &&grid[newRow][newCol] == "1") {dsu.merge(r * cols + c, newRow * cols + newCol); // 合并当前元素与相邻元素}}}}return dsu.count; // 返回连通块数量
}// 并查集类
class DisjointSet {constructor(size) {this.parent = Array.from({ length: size }, (_, i) => i); // 初始化父节点数组this.count = size; // 初始连通块数量}// 查找操作,带路径压缩find(p) {if (this.parent[p] !== p) {this.parent[p] = this.find(this.parent[p]); // 递归查找根节点并路径压缩}return this.parent[p];}// 合并操作merge(p, q) {const rootP = this.find(p); // 找到p的根节点const rootQ = this.find(q); // 找到q的根节点// 如果p和q不在同一集合中,将q的根节点连接到p的根节点if (rootP !== rootQ) {this.parent[rootQ] = rootP;this.count--; // 连通块数量减少}}
}
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏