【华为OD-E卷-开心消消乐 100分（python、java、c++、js、c）】
【华为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'，开始DFS
if 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++;
// 使用队列进行BFS
Queue<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]; // 新位置的列坐标
// 检查新位置是否在矩阵范围内且为1
if (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;
// 检查新位置是否在矩阵范围内且值为1
if (
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--; // 连通块数量减少
}
}
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏