问题
听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。
不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。
牛皮可用一个 N×M 的字符矩阵来表示,如下所示:
其中,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函数的具体作用是什么