华为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<m
• 0≤ci<n

输出描述

一个整数数组 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]

题解

思路：并查集

c++

#include<iostream>
#include<vector>
#include<string>
#include <utility>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;

// 找到连通块的代表节点
int find(int a, vector<int> &ans) {
if (ans[a] != a) {
ans[a] = find(ans[a], ans);
}
return ans[a];
}

// 合并两个组
void merge(int a, int b, vector<int> &ans) {
int rootA = find(a, ans);
int rootB = find(b, ans);
int newRoot = min(rootA, rootB);
ans[rootA] = newRoot;
ans[rootB] = newRoot;
}

int main() {
int m, n;
cin >> m >> n;
vector<int> grid(m * n, -1);
// 四个方向
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

int blockCount = 0;
int r, c;
vector<int> result;
// 忽略换行符
cin.ignore();

string line;
while (getline(cin, line)) {
if (line.empty()) continue;
int commaPos = line.find(',');
int r = stoi(line.substr(0, commaPos));
int c = stoi(line.substr(commaPos + 1));
int id = r * n + c;
// 之前已被标记为异常，不会影响
if (grid[id] != -1) {
result.push_back(blockCount);
continue;
}
// 标记为异常，正常来说会新增一个块
grid[id] = id;
blockCount++;

// 考虑合并块
for (auto &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)) {
continue;
}
// 不属于同一个块，进行合并, 两个块合并会减少一个区域
merge(id, nid, grid);
blockCount–;
}
result.push_back(blockCount);
}

// 输出结果
cout << "[";
for (int i = 0; i < result.size(); i++) {
cout << result[i];
if (i + 1 < result.size()) cout << ",";
}
cout<< "]";
}

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<Integer> 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 <stdio.h>
#include <string.h>
#include <stdlib.h>

// 查找异常块代表节点
int find(int a, int parent[]) {
if (parent[a] != a) {
parent[a] = find(parent[a], parent);
}
return parent[a];
}

// 合并两个连通块
void merge(int a, int b, int parent[]) {
int ra = find(a, parent);
int rb = find(b, parent);
int newRoot = ra < rb ? ra : rb;
parent[ra] = newRoot;
parent[rb] = newRoot;
}

int main() {
int m, n;
scanf("%d", &m);
scanf("%d", &n);
getchar(); // 吃掉换行

int size = m * n;
int parent[size];
for (int i = 0; i < size; i++) parent[i] = –1;
// 四个方向
int dirs[4][2] = {{–1,0}, {1,0}, {0,–1}, {0,1}};

int blockCount = 0;
int result[2000], resSize = 0;

char line[100];
while (fgets(line, sizeof(line), stdin)) {
if (line[0] == '\\n') continue;

int r, c;
sscanf(line, "%d,%d", &r, &c);
int id = r * n + c;
// 已经是异常点
if (parent[id] != –1) {
result[resSize++] = blockCount;
continue;
}

parent[id] = id;
blockCount++;

for (int i = 0; i < 4; i++) {
int nr = r + dirs[i][0];
int nc = c + dirs[i][1];
// 越界
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;

int nid = nr * n + nc;
// 不是异常点，不存在联通
if (parent[nid] == –1) continue;
// 不属于同一异常块，连通，数量-1
if (find(id, parent) != find(nid, parent)) {
merge(id, nid, parent);
blockCount—;
}
}

result[resSize++] = blockCount;
}

printf("[");
for (int i = 0; i < resSize; i++) {
if (i > 0) printf(",");
printf("%d", result[i]);
}
printf("]\\n");

return 0;
}