华为OD机试双机位C卷 - FLASH坏块监测系统 (C语言 & C++ & Python & JAVA & JS & GO)
FLASH坏块监测系统
华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解
题目描述
开发一个 FLASH 坏块监测系统，能够监测 FLASH 中坏块的数量。FLASH 介质以一个大小为 m×n的二维二进制矩阵表示，其中：0 表示正常，1 表示异常。最初，FLASH 介质中的所有单元格都是正常（即，所有单元格都是 0）。
系统运行过程中，FLASH 坏块不断产生：随着系统持续运行，某一个时刻 i，FLASH 介质中的某个单元格 (ri,ci)由正常变为异常。返回一个整数数组 result，其中 result[i] 是 FLASH 介质中第 i 个时刻 (ri,ci)位置变为异常后，FLASH 中坏块的数量。坏块的定义：坏块是由 4 个方向相连的异常单元格组成的“极大”块。你可以假设给定的 FLASH 介质外的所有点都是正常的。
输入描述
第一行输入和第二行输入分别为 m 和 n，表示 FLASH 介质是 m×n的二维二进制矩阵。
第三行开始的每一行表示第 ii 个时刻新增的异常位置 (ri,ci)最多 1000 个。
注意：
- 1≤m,n≤10^3
- 1≤m×n≤10^4
- 0≤ri
- 0≤ci
- 0≤ci
输出描述
一个整数数组 result，其中 result[i] 是 FLASH 介质中第 i 个时刻 (ri,ci)位置变为异常后，FLASH 中坏块的数量。
用例1
输入
4
3
1,1
2,2
3,2
0,2
1,2
输出
[1,2,2,3,1]
说明
起初，FLASH 介质被认为全部是正常的（0 代表正常，1 代表异常）。
时刻 1：位置 [1,1] 由正常状态变为异常状态。此时存在 1 个坏块。
时刻 2：位置 [2,2] 由正常状态变为异常状态。此时存在 2 个坏块。
时刻 3：位置 [3,2] 由正常状态变为异常状态。此时存在 2 个坏块。
时刻 4：位置 [0,2] 由正常状态变为异常状态。此时存在 3 个坏块。
时刻 5：位置 [1,2] 由正常状态变为异常状态。此时存在 1 个坏块。
示例二
输入
1
1
0,0
输出
[1]
题解
思路：并查集
- 这题主要是要分析出来一个规律，新增一个异常点会增加一个异常块，如果新增异常点的四周任意一个方向是异常块，就会产生异常块连通，两个异常块连通会导致总异常块数量-1.
- 根据1的规律，这道题就非常适合使用
并查集算法实现。具体逻辑如下：- 定义
blockCount = 0记录总异常块数量，定义grid[]数组存储每个点的状态(这里有个优化，用一维表示二维， 初始化所有点为-1，表示不是异常点)，定义result存储每个时刻总异常块数量 - 接下来就是接受异常点输入，然后根据以下逻辑处理
- 计算异常点位置
index = r * n + c - 判断
grid[index] == -1, 如果不等于-1，说明之前已经是异常点，不会产生任何影响直接跳过。否则进行grid[index] == index, blockCount++, 新增异常块 - 接下来判断新增点是否能够和四周点进行异常块的连通，接下来以左方向点为例逻辑为：
- 判断是否超过边界，超过跳过
- 判断是否为异常点，判断是否等于-1，是的话直接跳过
- 判断index位置和左方向点是否同属于一个异常块，是的话直接跳过。否则直接进行连通块合并，并减少
blockCount--,
- 通过
result记录连通块数量
- 计算异常点位置
- 输出结果
- 定义
c++
#include
#include
#include
#include
#include
#include
#include
#include JAVA
import java.io.*;
import java.util.*;
public class Main {
// 查找连通块代表节点（路径压缩）
static int find(int a, int[] parent) {
if (parent[a] != a) {
parent[a] = find(parent[a], parent);
}
return parent[a];
}
// 合并两个连通块
static void merge(int a, int b, int[] parent) {
int rootA = find(a, parent);
int rootB = find(b, parent);
int newRoot = Math.min(rootA, rootB);
parent[rootA] = newRoot;
parent[rootB] = newRoot;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(br.readLine().trim());
int n = Integer.parseInt(br.readLine().trim());
int[] grid = new int[m * n];
Arrays.fill(grid, -1);
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int blockCount = 0;
List result = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) continue;
String[] parts = line.split(",");
int r = Integer.parseInt(parts[0]);
int c = Integer.parseInt(parts[1]);
int id = r * n + c;
// 已经是异常
if (grid[id] != -1) {
result.add(blockCount);
continue;
}
// 新增异常点
grid[id] = id;
blockCount++;
// 合并相邻异常块
for (int[] d : dirs) {
int nr = r + d[0];
int nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int nid = nr * n + nc;
if (grid[nid] == -1) continue;
if (find(id, grid) != find(nid, grid)) {
merge(id, nid, grid);
blockCount--;
}
}
result.add(blockCount);
}
// 输出结果
System.out.print("[");
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i));
if (i + 1 < result.size()) System.out.print(",");
}
System.out.println("]");
}
}
Python
import sys
# 查找代表节点（路径压缩）
def find(a, parent):
if parent[a] != a:
parent[a] = find(parent[a], parent)
return parent[a]
# 合并两个集合
def merge(a, b, parent):
ra = find(a, parent)
rb = find(b, parent)
new_root = min(ra, rb)
parent[ra] = new_root
parent[rb] = new_root
def main():
lines = sys.stdin.read().strip().splitlines()
if not lines:
return
m = int(lines[0])
n = int(lines[1])
grid = [-1] * (m * n)
# 四个方向
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
block_count = 0
result = []
for line in lines[2:]:
if not line.strip():
continue
r, c = map(int, line.split(','))
id = r * n + c
# 已经是异常，不会影响
if grid[id] != -1:
result.append(block_count)
continue
grid[id] = id
block_count += 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
# 越界
if nr < 0 or nr >= m or nc < 0 or nc >= n:
continue
nid = nr * n + nc
# 不是异常的
if grid[nid] == -1:
continue
# 不属于同一个异常块，合并， 异常块数量-1
if find(id, grid) != find(nid, grid):
merge(id, nid, grid)
block_count -= 1
result.append(block_count)
print("[" + ",".join(map(str, result)) + "]")
if __name__ == "__main__":
main()
JavaScript
'use strict';
const readline = require('readline');
// 创建 readline 接口
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
const lines = [];
rl.on('line', (line) => {
lines.push(line.trim());
});
rl.on('close', () => {
if (lines.length === 0) return;
let idx = 0;
const m = parseInt(lines[idx++]);
const n = parseInt(lines[idx++]);
// grid 同时作为「是否异常」和「并查集 parent」
const grid = new Array(m * n).fill(-1);
// 四个方向
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
// 查找代表节点（路径压缩）
function find(a) {
if (grid[a] !== a) {
grid[a] = find(grid[a]);
}
return grid[a];
}
// 合并两个连通块
function merge(a, b) {
const rootA = find(a);
const rootB = find(b);
const newRoot = Math.min(rootA, rootB);
grid[rootA] = newRoot;
grid[rootB] = newRoot;
}
let blockCount = 0;
const result = [];
// 处理后续每一行 "r,c"
while (idx < lines.length) {
const line = lines[idx++].trim();
if (!line) continue;
const [r, c] = line.split(',').map(Number);
const id = r * n + c;
// 已经是异常块
if (grid[id] !== -1) {
result.push(blockCount);
continue;
}
// 新增异常点
grid[id] = id;
blockCount++;
// 合并四邻域
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
const nid = nr * n + nc;
if (grid[nid] === -1) continue;
if (find(id) !== find(nid)) {
merge(id, nid);
blockCount--;
}
}
result.push(blockCount);
}
// 输出结果
console.log("[" + result.join(",") + "]");
});
Go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
// 查找异常块的代表节点
func find(a int, parent []int) int {
if parent[a] != a {
parent[a] = find(parent[a], parent)
}
return parent[a]
}
// 合并两个异常块
func merge(a, b int, parent []int) {
ra := find(a, parent)
rb := find(b, parent)
newRoot := ra
if rb < ra {
newRoot = rb
}
parent[ra] = newRoot
parent[rb] = newRoot
}
func main() {
in := bufio.NewScanner(os.Stdin)
in.Scan()
m, _ := strconv.Atoi(strings.TrimSpace(in.Text()))
in.Scan()
n, _ := strconv.Atoi(strings.TrimSpace(in.Text()))
grid := make([]int, m*n)
for i := range grid {
grid[i] = -1
}
// 四个方向
dirs := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
blockCount := 0
result := []int{}
for in.Scan() {
line := strings.TrimSpace(in.Text())
if line == "" {
continue
}
parts := strings.Split(line, ",")
r, _ := strconv.Atoi(parts[0])
c, _ := strconv.Atoi(parts[1])
id := r*n + c
// 已经是异常点，不会造成影响
if grid[id] != -1 {
result = append(result, blockCount)
continue
}
grid[id] = id
blockCount++
for _, d := range dirs {
nr := r + d[0]
nc := c + d[1]
// 越界
if nr < 0 || nr >= m || nc < 0 || nc >= n {
continue
}
nid := nr*n + nc
// 不是异常点，不存在连通
if grid[nid] == -1 {
continue
}
// 连通两个异常块，数量-1
if find(id, grid) != find(nid, grid) {
merge(id, nid, grid)
blockCount--
}
}
result = append(result, blockCount)
}
fmt.Print("[")
for i, v := range result {
if i > 0 {
fmt.Print(",")
}
fmt.Print(v)
}
fmt.Println("]")
}
C语言
#include 
