冷たい飲み物

-質問

N*Mサイズの氷棚があります.穿孔した部分は0、仕切りがある部分は1と表示されます.穿孔された部分の間が上、下、左、右で接続されている場合は、相互接続とみなされます.所定の氷棚の形状で生成されるアイスクリームの総数を求めるプログラムを作成してください.

-入力条件

の第1列は、氷棚の縦長Nおよび横長Mを与える.(1 <= N, M <= 1,000)

の第2列からN+1列に氷棚の形態が与えられる.

このとき、2つのうっ血の部分は0であり、そうでない部分は1である.

-出力条件

一度に作れるアイスクリームの数を出力します.

-入力例

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

-出力例

8

-問題を解く

この問題はDFSで解決できる.まず、凍結した空間を上、下、左、右接続として表すことができるので、図形形式でモデリングすることができる.
プロセスを順番にリストします.
1.サイトの周囲の上、下、左、右を表示します.「0」の値を持つが、まだアクセスしていない場所がある場合は、そのサイトにアクセスします.
2.アクセスポイントで上、下、左、右を再表示し、すべての接続ポイントにアクセスできます.
3.すべてのノードに対して1～2回のプロセスを繰り返し、アクセスされていないポイントの数を計算します.

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False

    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True

    return False

n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1

print(result)

出典:これは就職のためのコードテストで、Python、羅東彬知音で