题解 | 挡住洪水

感觉题目有歧义....是统计不会被淹的0的数量不是区域的数量。

from collections import deque

def in_bound(x, y, n, m):
    return 0 <= x < n and 0 <= y < m


n, m = map(int, input().split())
maze = [list(input()) for _ in range(n)]

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

visited = [[False] * m for _ in range(n)]
blocks = []

q = deque()
k = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == '0' and not visited[i][j]:
            blocks.append([])
            visited[i][j] = True
            q.append((i,j))
            k += 1
            blocks[-1].append((i,j))
            while q:
                x, y = q.popleft()
                for p in range(4):
                    nx = x + dx[p]
                    ny = y + dy[p]
                    if in_bound(nx,ny,n,m) and not visited[nx][ny] and maze[nx][ny] == '0':
                        visited[nx][ny] = True
                        q.append((nx,ny))
                        blocks[-1].append((nx,ny))

cnt = 0
for block in blocks:
    flag = True
    for points in block:
        x, y = points[0],points[1]
        if  (x == 0 or x == n-1) or (y == 0 or y == m-1):
            flag = False
            break
    if flag:
        cnt += len(block)
print(cnt)