【华为OD-E卷-11 开心消消乐 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
输出：
1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
用例二：
输入：
4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
输出：
2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

python解法

解题步骤：
使用深度优先搜索（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)

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

遍历整个矩阵，找到值为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;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

具体步骤：
并查集初始化：将矩阵中每个元素映射为一维数组中的一个节点，构建并查集，每个节点初始时自成一个集合。
矩阵遍历：
对于每个值为1的元素，检查其八个方向上的相邻元素。
如果相邻元素值为1，将当前元素和相邻元素合并到同一集合中。
如果当前元素为0，则直接减少集合计数。
计数连通块：并查集中最终剩余的集合数即为连通块的数量。
优势：
使用并查集，能够高效处理连通块合并操作。
每次union操作和find操作的时间复杂度接近 O(1)（通过路径压缩和按秩合并优化）。

#include 
#include 

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;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

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--; // 连通块数量减少
    }
  }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144538297"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！