在线评测链接:P1147

前言

​ 第一题太水了，群友已经忘记内容了。想必应该也是个人均都会的签到题。大家从第二题开始看吧

题目内容

塔子哥是一个年轻的程序员，他热爱计算机科学和数学。他一直在思考如何利用计算机技术来解决实际问题。有一天，他接到了一项任务，要为一个遥远的星球上的一座城市设计一个城市规划系统。

这个城市非常大，由许多小区域组成。每个小区域都有一个 $n\ast m$ 的矩阵，矩阵中的每个位置都取值为 $W$ 或 $R$，分别代表白色和红色。这些小区域之间可能存在道路或其他障碍物，但每个小区域内部都是连通的。

塔子哥想知道，如果将任意位置 $(i,j)$ 涂成白色后，会有多少个全红的连通块，求一个 $n\ast m$ 的矩阵 $ans$ ， $ans[i][j]$ 表示将位置 $(i,j)$ 涂成白色以后，剩下的全红连通块个数。 保证数据随机生成

输入描述

第一行为两个整数 $n$ 和 $m$ ，（ $1\le n,m\le 40$ ）

接下来 $n$ 行，每行有 $m$ 个字母，每个字母取值为 $W$ 或 $R$ 。

输出描述

输出为一个 $n\ast m$ 的矩阵。

样例

输入

4 3
R W W
W R R
R R R
W W W

输出

1 2 2 
2 2 2 
2 3 2 
2 2 2 

思路:bfs/dfs/并查集求联通块个数

非常经典的题。枚举所有点，把它改成白色，然后求一遍联通块个数。

复杂度:$O(nm\ast nm)=O(n^2{m}^2)$

拓展:$n,m=1e3$ 如何做?

1.学习割点:割点和桥 - Oi Wiki

2.原题来自:D.Router Mesh - 2020 ICPC小米选拔赛第一场

类似题目推荐

LeetCode

剑指 Offer II 105. 岛屿的最大面积

200. 岛屿数量

547. 朋友圈

CodeFun2000

P1094. 米哈游 2023.03.19-第一题-塔子哥的RBG矩阵

P1237 2023.04.15-美团实习-第三题-交通规划

代码

C++

#include <bits/stdc++.h>
using namespace std;const int maxn = 45, dirs[4][2]{-1, 0, 1, 0, 0, -1, 0, 1};
char colors[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
void dfs(int x, int y) {vis[x][y] = true;for (auto &[dx, dy] : dirs) {int nx = x + dx, ny = y + dy;if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && colors[nx][ny] == 'R') {dfs(nx, ny);}}
}// 求联通分量个数
int solve() {memset(vis, 0, sizeof(vis));int cnt = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (vis[i][j] || colors[i][j] == 'W') continue;dfs(i, j);cnt++;}}return cnt;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> colors[i][j];}}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {char preColor = colors[i][j];colors[i][j] = 'W';int cnt = solve();printf("%d ", cnt);colors[i][j] = preColor;}printf("\n");}return 0;
}
// by yhy

python

dfs解法

n , m = list(map(int , input().split()))
a = []
for i in range(n):a.append(list(map(str , input().split())))
dx = [0 , 0 , -1 , 1]
dy = [-1 , 1 , 0 , 0]
bk = set()
# dfs 求联通块个数
def dfs (x , y):bk.add(f"{x} {y}")for i in range (4):nx = x + dx[i]ny = y + dy[i]if nx < 0 or nx >= n or ny < 0 or ny >= m or f"{nx} {ny}" in bk or a[nx][ny] == 'W':continuedfs(nx , ny)
def calc (x , y):bk.clear()t = a[x][y]a[x][y] = 'W'cnt = 0for i in range (n):for j in range (m):if f"{i} {j}" in bk or a[i][j] == 'W':continuedfs(i , j)cnt += 1a[x][y] = treturn cntfor i in range (n):for j in range (m):print (calc(i , j) , end = "")if j == m - 1:print()else:print(" " , end = "")

Java

并查集解法

import java.util.*;public class Main {static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向static int[] father; // 并查集数组static int countRedBlocks; // 红色连通块个数public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();scanner.nextLine(); // 读取换行符char[][] matrix = new char[n][m];for (int i = 0; i < n; i++) {matrix[i] = scanner.nextLine().replaceAll(" ", "").toCharArray();}int[][] ans = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == 'R') {// 将颜色为 W 的格子修改为 Rmatrix[i][j] = 'W';// 统计剩余的红色连通块个数ans[i][j] = countRedBlocks(matrix, n, m);// 将颜色再改回来，以便下一次统计matrix[i][j] = 'R';} else {ans[i][j] = countRedBlocks(matrix, n, m);}}}// 输出结果for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {System.out.print(ans[i][j] + " ");}System.out.println();}}// 计算红色连通块个数private static int countRedBlocks(char[][] matrix, int n, int m) {// 初始化并查集father = new int[n * m];countRedBlocks = 0;for (int i = 0; i < n * m; i++) {father[i] = i;if (matrix[i / m][i % m] == 'R') {countRedBlocks++;}}// 合并相邻格子中的红色连通块for (int i = 0; i < n * m; i++) {int x1 = i / m;int y1 = i % m;if (matrix[x1][y1] == 'R') {for (int[] dir : dirs) {int x2 = x1 + dir[0];int y2 = y1 + dir[1];if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && matrix[x2][y2] == 'R') {int p1 = find(i);int p2 = find(x2 * m + y2);if (p1 != p2) {father[p1] = p2;countRedBlocks--;}}}}}return countRedBlocks;}// 查找节点的根节点，并进行路径压缩优化private static int find(int u) {if (u != father[u]) {father[u] = find(father[u]);}return father[u];}
}

Go

package mainimport ("bufio""fmt""os"
)var dx = []int{0, 0, -1, 1}
var dy = []int{-1 , 1 , 0 , 0}
var bk = make(map[string]bool)
var a [][]string
var n, m int
// dfs求联通块
func dfs(x, y int) {bk[fmt.Sprintf("%d %d", x, y)] = truefor i := 0; i < 4; i++ {nx := x + dx[i]ny := y + dy[i]if nx < 0 || nx >= n || ny < 0 || ny >= m || bk[fmt.Sprintf("%d %d", nx, ny)] || a[nx][ny] == "W" {continue}dfs(nx, ny)}
}
// 将这个点涂白，求解连通分量个数
func calc(x, y int) int {bk = make(map[string]bool)t := a[x][y]a[x][y] = "W"cnt := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if bk[fmt.Sprintf("%d %d", i, j)] || a[i][j]  == "W" {continue}dfs(i, j)cnt++}}a[x][y] = treturn cnt
}
func main() {reader := bufio.NewReader(os.Stdin)fmt.Scanf("%d %d\n", &n, &m)a = make([][]string, n)for i := 0; i < n; i++ {a[i] = make([]string, m)line, _ := reader.ReadString('\n')for j := 0; j < m; j++ {fmt.Sscanf(string(line[j*2:j*2+1]), "%s", &a[i][j])}}for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Printf("%d", calc(i, j))if j == m-1 {fmt.Println()} else {fmt.Print(" ")}}}
}

Js

let input = "";
process.stdin.resume();
process.stdin.setEncoding("utf-8");process.stdin.on("data", (data) => {input += data;
});process.stdin.on("end", () => {const lines = input.trim().split("\n");const [n, m] = lines[0].trim().split(" ").map(Number);const a = [];for (let i = 1; i <= n; i++) {const row = lines[i].trim().split(" ");a.push(row);}// dfs 求联通块个数const dx = [0, 0, -1, 1];const dy = [-1, 1, 0, 0];const bk = new Set();function dfs(x, y) {bk.add(`${x} ${y}`);for (let i = 0; i < 4; i++) {const nx = x + dx[i];const ny = y + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= m || bk.has(`${nx} ${ny}`) || a[nx][ny] === "W") {continue;}dfs(nx, ny);}}// 将[x,y] 涂成白色 ，求连通分量个数function calc(x, y) {bk.clear();const t = a[x][y];a[x][y] = "W";let cnt = 0;for (let i = 0; i < n; i++) {for (let j = 0; j < m; j++) {if (bk.has(`${i} ${j}`) || a[i][j] === "W") {continue;}dfs(i, j);cnt++;}}a[x][y] = t;return cnt;}for (let i = 0; i < n; i++) {let rowOutput = "";for (let j = 0; j < m; j++) {rowOutput += calc(i, j);if (j === m - 1) {rowOutput += "\n";} else {rowOutput += " ";}}process.stdout.write(rowOutput);}
});