)
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]题解
思路：并查集
- 这题主要是要分析出来一个规律，新增一个异常点会增加一个异常块，如果新增异常点的四周任意一个方向是异常块，就会产生异常块连通，两个异常块连通会导致总异常块数量-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<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
importsys# 查找代表节点（路径压缩）deffind(a,parent):ifparent[a]!=a:parent[a]=find(parent[a],parent)returnparent[a]# 合并两个集合defmerge(a,b,parent):ra=find(a,parent)rb=find(b,parent)new_root=min(ra,rb)parent[ra]=new_root parent[rb]=new_rootdefmain():lines=sys.stdin.read().strip().splitlines()ifnotlines:returnm=int(lines[0])n=int(lines[1])grid=[-1]*(m*n)# 四个方向dirs=[(-1,0),(1,0),(0,-1),(0,1)]block_count=0result=[]forlineinlines[2:]:ifnotline.strip():continuer,c=map(int,line.split(','))id=r*n+c# 已经是异常，不会影响ifgrid[id]!=-1:result.append(block_count)continuegrid[id]=idblock_count+=1fordr,dcindirs:nr,nc=r+dr,c+dc# 越界ifnr<0ornr>=mornc<0ornc>=n:continuenid=nr*n+nc# 不是异常的ifgrid[nid]==-1:continue# 不属于同一个异常块，合并， 异常块数量-1iffind(id,grid)!=find(nid,grid):merge(id,nid,grid)block_count-=1result.append(block_count)print("["+",".join(map(str,result))+"]")if__name__=="__main__":main()JavaScript
'use strict';constreadline=require('readline');// 创建 readline 接口constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on('line',(line)=>{lines.push(line.trim());});rl.on('close',()=>{if(lines.length===0)return;letidx=0;constm=parseInt(lines[idx++]);constn=parseInt(lines[idx++]);// grid 同时作为「是否异常」和「并查集 parent」constgrid=newArray(m*n).fill(-1);// 四个方向constdirs=[[-1,0],[1,0],[0,-1],[0,1]];// 查找代表节点（路径压缩）functionfind(a){if(grid[a]!==a){grid[a]=find(grid[a]);}returngrid[a];}// 合并两个连通块functionmerge(a,b){constrootA=find(a);constrootB=find(b);constnewRoot=Math.min(rootA,rootB);grid[rootA]=newRoot;grid[rootB]=newRoot;}letblockCount=0;constresult=[];// 处理后续每一行 "r,c"while(idx<lines.length){constline=lines[idx++].trim();if(!line)continue;const[r,c]=line.split(',').map(Number);constid=r*n+c;// 已经是异常块if(grid[id]!==-1){result.push(blockCount);continue;}// 新增异常点grid[id]=id;blockCount++;// 合并四邻域for(const[dr,dc]ofdirs){constnr=r+dr;constnc=c+dc;if(nr<0||nr>=m||nc<0||nc>=n)continue;constnid=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
packagemainimport("bufio""fmt""os""strconv""strings")// 查找异常块的代表节点funcfind(aint,parent[]int)int{ifparent[a]!=a{parent[a]=find(parent[a],parent)}returnparent[a]}// 合并两个异常块funcmerge(a,bint,parent[]int){ra:=find(a,parent)rb:=find(b,parent)newRoot:=raifrb<ra{newRoot=rb}parent[ra]=newRoot parent[rb]=newRoot}funcmain(){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)fori:=rangegrid{grid[i]=-1}// 四个方向dirs:=[][]int{{-1,0},{1,0},{0,-1},{0,1}}blockCount:=0result:=[]int{}forin.Scan(){line:=strings.TrimSpace(in.Text())ifline==""{continue}parts:=strings.Split(line,",")r,_:=strconv.Atoi(parts[0])c,_:=strconv.Atoi(parts[1])id:=r*n+c// 已经是异常点，不会造成影响ifgrid[id]!=-1{result=append(result,blockCount)continue}grid[id]=id blockCount++for_,d:=rangedirs{nr:=r+d[0]nc:=c+d[1]// 越界ifnr<0||nr>=m||nc<0||nc>=n{continue}nid:=nr*n+nc// 不是异常点，不存在连通ifgrid[nid]==-1{continue}// 连通两个异常块，数量-1iffind(id,grid)!=find(nid,grid){merge(id,nid,grid)blockCount--}}result=append(result,blockCount)}fmt.Print("[")fori,v:=rangeresult{ifi>0{fmt.Print(",")}fmt.Print(v)}fmt.Println("]")}C语言
#include<stdio.h>#include<string.h>#include<stdlib.h>// 查找异常块代表节点intfind(inta,intparent[]){if(parent[a]!=a){parent[a]=find(parent[a],parent);}returnparent[a];}// 合并两个连通块voidmerge(inta,intb,intparent[]){intra=find(a,parent);intrb=find(b,parent);intnewRoot=ra<rb?ra:rb;parent[ra]=newRoot;parent[rb]=newRoot;}intmain(){intm,n;scanf("%d",&m);scanf("%d",&n);getchar();// 吃掉换行intsize=m*n;intparent[size];for(inti=0;i<size;i++)parent[i]=-1;// 四个方向intdirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};intblockCount=0;intresult[2000],resSize=0;charline[100];while(fgets(line,sizeof(line),stdin)){if(line[0]=='\n')continue;intr,c;sscanf(line,"%d,%d",&r,&c);intid=r*n+c;// 已经是异常点if(parent[id]!=-1){result[resSize++]=blockCount;continue;}parent[id]=id;blockCount++;for(inti=0;i<4;i++){intnr=r+dirs[i][0];intnc=c+dirs[i][1];// 越界if(nr<0||nr>=m||nc<0||nc>=n)continue;intnid=nr*n+nc;// 不是异常点，不存在联通if(parent[nid]==-1)continue;// 不属于同一异常块，连通，数量-1if(find(id,parent)!=find(nid,parent)){merge(id,nid,parent);blockCount--;}}result[resSize++]=blockCount;}printf("[");for(inti=0;i<resSize;i++){if(i>0)printf(",");printf("%d",result[i]);}printf("]\n");return0;}
