这张网格有几个岛
四行四列,1 是陆地 0 是海。上下左右相邻算同一个岛。运行下面这段程序,看岛数 / 最大的岛多大 / 陆地总格数:
def islands(g, dirs):
m = len(g)
n = len(g[0])
seen = set()
cnt = 0
sizes = []
for i in range(m):
for j in range(n):
if g[i][j] != 1 or (i, j) in seen:
continue
cnt += 1
st = [(i, j)]
seen.add((i, j))
sz = 0
while st:
x, y = st.pop()
sz += 1
for dx, dy in dirs:
a, b = x + dx, y + dy
if (0 <= a < m and 0 <= b < n
and g[a][b] == 1 and (a, b) not in seen):
seen.add((a, b))
st.append((a, b))
sizes.append(sz)
return cnt, sizes
D4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
D8 = D4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))
g = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 0], [1, 0, 0, 0]]
c, sz = islands(g, D4)
print(str(c) + "/" + str(max(sz)) + "/" + str(sum(sz)))
全部评论