算法1
并查集
Python 代码
def find(a):
if a == parent[a]:
return a
par = find(parent[a])
parent[a] = par
return par
def union(a, b):
ap = find(a)
bp = find(b)
if ap != bp:
parent[ap] = bp
cnt[bp] += cnt[ap]
while True:
m, n = map(int, input().split())
if m == n == 0:
break
parent = [i for i in range(m * n)]
cnt = [1] * (m * n)
arr = []
for i in range(n):
arr.append(input())
x, y = 0, 0
for i in range(n):
for j in range(m):
if arr[i][j] == '@':
x, y = i, j
if arr[i][j] != '#':
if i < n - 1 and arr[i + 1][j] in ['.', '@']:
union(i * m + j, (i + 1) * m + j)
if j < m - 1 and arr[i][j + 1] in ['.', '@']:
union(i * m + j, i * m + j + 1)
print(cnt[find(x * m + y)])
算法2
BFS
Python 代码
from _collections import deque
while True:
m, n = map(int, input().split())
if m == n == 0:
break
arr = []
for _ in range(n):
arr.append(list(input()))
x = y = 0
for i in range(n):
for j in range(m):
if arr[i][j] == '@':
x, y = i, j
break
queue = deque()
queue.append((x, y))
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
ans = 1
while queue:
currX, currY = queue.pop()
for i, j in direction:
nx, ny = currX + i, currY + j
if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == '.':
queue.append((nx, ny))
arr[nx][ny] = 'v'
ans += 1
print(ans)
算法3
DFS
Python 代码
def dfs(x, y):
global ans
ans += 1
for i, j in direction:
nx, ny = x + i, y + j
if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == '.':
arr[nx][ny] = 'v'
dfs(nx, ny)
while True:
m, n = map(int, input().split())
if m == n == 0:
break
arr = []
for _ in range(n):
arr.append(list(input()))
x = y = 0
for i in range(n):
for j in range(m):
if arr[i][j] == '@':
x, y = i, j
break
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
ans = 0
dfs(x, y)
print(ans)
兄弟,并查集解这道题的思路是什么呀?
看不太懂你的代码
并查集解法就是遍历每个点,如果该点的右方和下方和该点连通则进行union操作,cnt数组记录该点所在岛屿的数量。