sunflower758 2022-02-19 15:20 采纳率: 86.5%
浏览 34
已结题

python算法题,bfs dfs相关的吧

问题
听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。

不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。

牛皮可用一个 N×M 的字符矩阵来表示,如下所示:

img

其中,X 表示斑点部分。

如果两个 X 在垂直或水平方向上相邻(对角相邻不算在内),则它们属于同一个斑点,由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色,将两个斑点合为一个。

在上面的例子中,他只需要给三个 . 区域内涂色即可(新涂色区域用 ∗ 表示):

请帮助约翰确定,为了使两个斑点合为一个,他需要涂色区域的最少数量。

输入格式
第一行包含两个整数 N 和 M。

接下来 N 行,每行包含一个长度为 M 的由 X 和 . 构成的字符串,用来表示描述牛皮图案的字符矩阵。

输出格式
输出需要涂色区域的最少数量。

数据范围
1≤N,M≤50
答案:


```python
import sys

n, m = map(int, sys.stdin.readline().split())
mat = [sys.stdin.readline().strip() for _ in range(n)]

N = n * m
f = list(range(N))
def find(i):
    if i != f[i]:
        f[i] = find(f[i])
    return f[i]

def union(i, j):
    fi, fj = find(i), find(j)
    if fi > fj:
        fj, fi = fi, fj
    f[fj] = fi

for i in range(n):
    for j in range(m):
        if mat[i][j] == '.':
            continue
        ij = i * m + j
        if i > 0 and mat[i-1][j] == 'X':
            union(ij - m, ij)
        if j > 0 and mat[i][j-1] == 'X':
            union(ij - 1, ij)

from collections import *
mp = defaultdict(set)

for i in range(n):
    for j in range(m):
        if mat[i][j] == 'X':
            mp[find(i * m + j )].add((i, j))

s1, s2 = mp.values()

def solve():
    q = deque(list(s1))
    ans = -1
    while q:
        ans += 1
        for _ in range(len(q)):
            i, j = q.popleft()
            for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
                ii, jj = i + di, j + dj
                if 0 <= ii < n and 0 <= jj < m and (ii, jj) not in s1:
                    if (ii, jj) in s2:
                        return ans
                    s1.add((ii, jj))
                    q.append((ii, jj))

print(solve())





问题:
1,按题目输入,得到的f序列[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 18, 18, 18, 22, 23, 24, 25, 26, 26, 26, 29, 30, 31, 32, 33, 34, 18, 18, 18, 18, 39, 40, 41, 42, 26, 26, 45, 46, 47, 48, 18, 49, 18, 18, 53, 54, 55, 56, 57, 58, 26, 26, 26, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 26, 26, 26, 26, 26, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 26, 26, 26, 92, 93, 94, 95]
请问“18,49,18,18”怎么得到的
2.find函数的具体作用是什么

  • 写回答

1条回答 默认 最新

  • SmallAntJ 2022-02-19 20:26
    关注

    题主贴的代码是使用并查集实现的,列表f是并查集的数据结构,f存储的是每个像素点所属的集合,union函数和find函数是并查集的两种基本操作,建议先学习下并查集。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月6日
  • 已采纳回答 2月26日
  • 创建了问题 2月19日

悬赏问题

  • ¥15 windows2019+nginx+php耗时久
  • ¥15 labelme打不开怎么办
  • ¥35 按照图片上的两个任务要求,用keil5写出运行代码,并在proteus上仿真成功,🙏
  • ¥15 免费的电脑视频剪辑类软件如何盈利
  • ¥30 MPI读入tif文件并将文件路径分配给各进程时遇到问题
  • ¥15 pycharm中导入模块出错
  • ¥20 Ros2 moveit2 Windows环境配置,有偿,价格可商议。
  • ¥15 有关“完美的代价”问题的代码漏洞
  • ¥15 请帮我看一下这个简易化学配平器的逻辑有什么问题吗?
  • ¥15 暴力法无法解出,可能要使用dp和数学知识