【華為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]

輸出描述

輸出一個整數，表示最少需要點擊的次數

用例

用例一：

輸入：

輸出：

用例二：

輸入：

輸出：

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且在上下左右或對角線方向相鄰的元素視為同一連通塊。采用并查集（Disjoint Set Union, DSU）來解決。

核心思路：
并查集初始化：
將二維矩陣中的每個元素映射到一維數組，構建一個并查集。
初始時，每個元素自成一個集合。
遍歷矩陣：
對于矩陣中值為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--; // 連通塊數量減少}}
}