M05585: 晶矿的个数

matrices/dfs similar, http://cs101.openjudge.cn/practice/05585

在某个区域发现了一些晶矿，已经探明这些晶矿总共有分为两类，为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域，若m[i][j]为#表示该地点是非晶矿地点，若m[i][j]为r表示该地点是红晶矿地点，若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图，求红晶矿和黑晶矿的个数。

输入

第一行为k，表示有k组测试输入。每组第一行为n，表示该区域由n*n个地点组成，3 <= n<= 30 接下来n行，每行n个字符，表示该地点的类型。

输出

对每组测试数据输出一行，每行两个数字分别是红晶矿和黑晶矿的个数，一个空格隔开。

样例输入

2
6
r##bb#
###b##
#r##b#
#r##b#
#r####
######
4
####
#rrb
#rr#
##bb

样例输出

2 2
1 2

python

dire = [[-1,0], [1,0], [0,-1], [0,1]]

def dfs(x, y, c):
    m[x][y] = '#'
    for i in range(len(dire)):
        tx = x + dire[i][0]
        ty = y + dire[i][1]
        if m[tx][ty] == c:
            dfs(tx, ty, c)

for _ in range(int(input())):
    n = int(input())
    m = [[0 for _ in range(n+2)] for _ in range(n+2)]

    for i in range(1, n+1):
        m[i][1:-1] = input()

    r = 0 ; b=0
    for i in range(1, n+1):
        for j in range(1, n+1):
            if m[i][j] == 'r':
                dfs(i, j, 'r')
                r += 1
            if m[i][j] == 'b':
                dfs(i,j,'b')
                b += 1
    print(r, b)

通过使用栈来模拟递归，可以避免因递归过深导致的栈溢出问题。

python

import sys

# 定义方向数组
dire = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def dfs(x, y, c):
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        if m[x][y] != c:
            continue
        m[x][y] = '#'
        for dx, dy in dire:
            tx, ty = x + dx, y + dy
            if m[tx][ty] == c:
                stack.append((tx, ty))

# 处理多组测试数据
t = int(input())
for _ in range(t):
    n = int(input())
    
    # 初始化矩阵并添加边界
    m = [['.'] * (n + 2) for _ in range(n + 2)]
    for i in range(1, n + 1):
        m[i][1:-1] = list(input().strip())

    r = 0
    b = 0

    # 遍历矩阵
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if m[i][j] == 'r':
                dfs(i, j, 'r')
                r += 1
            elif m[i][j] == 'b':
                dfs(i, j, 'b')
                b += 1

    print(r, b)

并查集写法。小规模静态连通块问题 → DFS/BFS。
大规模或动态连通性问题 → 并查集

python

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1


def count_mines(grid, n):
    uf = UnionFind(n * n)
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for i in range(n):
        for j in range(n):
            if grid[i][j] in ('r', 'b'):
                for dx, dy in dirs:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == grid[i][j]:
                        uf.union(i * n + j, ni * n + nj)

    red_roots, black_roots = set(), set()
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 'r':
                red_roots.add(uf.find(i * n + j))
            elif grid[i][j] == 'b':
                black_roots.add(uf.find(i * n + j))
    return len(red_roots), len(black_roots)


# 主程序
k = int(input())
for _ in range(k):
    n = int(input())
    grid = [list(input().strip()) for _ in range(n)]
    r_count, b_count = count_mines(grid, n)
    print(r_count, b_count)

M05585: 晶矿的个数 ​

M05585: 晶矿的个数