污染海域

题目描述

有一片海域划分为N * M个方格，其中有些海域已被污染（用0表示），有些海域没被污染（用1表示）。

请问这片N * M海域中有几块是没被污染的独立海域（没被污染的独立海域是指该块海域上下左右被已污染的海域包围，且N * M以外的海域都为已被污染的海域）

例如：N=4，M=5，4 * 5的海域中，已被污染海域和没被污染的海域如下图：

这块4 * 5的海域，有3块海域（绿色）没被污染，因为每一块的上下左右都被污染的海域包围。

输入描述

第一行输入两个正整数N和M，N表示矩阵方格的行，M表示矩阵方格的列，N和M之间以一个英文逗号隔开；

第二行开始输入N行，每行M个数字（数字只能为1或者0，1表示没被污染的海域，0表示已被污染的海域）

输出描述

输出一个整数，表示N * M的海域中有几块是没被污染的独立海域

样例输入

4,5

1,1,0,0,0

1,0,1,0,0

1,0,0,0,0

1,1,0,1,1

样例输出

3

代码详解

展开查看

N, M = [int(i) for i in input().split(",")]
ls = [[int(i) for i in input().split(',')] for i in range(N)]

v = [[0] * M for i in range(N)] #记录探索结果

def dfs(x, y):
    v[x][y] = 1
    for  dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        xx = x + dx
        yy = y + dy
        if 0<=xx<N and 0<=yy<M and ls[xx][yy] == 1 and v[xx][yy] == 0:
            dfs(xx, yy)

cnt = 0
for i in range(N):
    for j in range(M):
        if ls[i][j] == 1 and v[i][j] == 0:
            dfs(i, j)
            cnt += 1

print(cnt)

运行结果

展开查看

4,5
1,1,0,0,0
1,0,1,0,0
1,0,0,0,0
1,1,0,1,1
3