[アルゴリズム]4963島の数

9966 ワード
baekjoon Python3 silver2 白駿 algorithm テキストリンク

投稿の作成を選択して問題を復習する基準は<解決済みです.ac天銀2(Silver 2)以上>.
※この写真と投稿内容の問題はすべて『Baekjoon OnlineJudge』から抜粋しています.

に質問


Baekjoonオンラインローエンド:4963島の数

ほどく


My Code


メモリ:32452 KB
時間:116ミリ秒
  • 「横、縦、対角線接続」▶dxとdy、移動方向操作
    • 島の形態を表す入力値はmに設定される.
    各陸地の開始座標についてvisitedで検査を行い、後で島の数を繰り返し検査しないようにする(定義関数bfs)
    import sys
input = sys.stdin.readline
dx =[0,0,1,-1, 1,1,-1,-1]
dy =[1,-1,0,0, 1,-1,1,-1]

from collections import deque

def bfs(w,h) :
    q = deque()
    q.append([h, w])
    visited[h][w] = 1
    while q:
        h, w = q.popleft()
        for i in range(8):
            nw = w + dx[i]
            nh = h + dy[i]
            if 0 <= nw < W and 0 <= nh < H:
                if m[nh][nw] == 1 and visited[nh][nw] == 0:
                    visited[nh][nw] = 1
                    q.append([nh, nw])


while True :
    W, H = map(int, input().split())
    if W==0 and H ==0 :
        break
    m = []
    visited = [[0]*W for _ in range(H)]
    for _ in range(H) :
        m.append(list(map(int, input().split())))

    land=0
    for i in range(H):
        for k in range(W) :
            if m[i][k] == 1 and visited[i][k] == 0 :
                bfs(k,i)
                land+=1
    print(land)
    Unit testing for Data Science in Python
    Day 057