사각형으로 구성된 섬과 바다의 지도를 얻을 수 있습니다.
섬의 수를 세는 프로그램을 작성하세요.
정사각형에 가로, 세로 또는 대각선으로 연결된 정사각형은 보행 가능한 정사각형입니다.
두 개의 사각형이 같은 섬에 있으려면 한 사각형에서 다른 사각형까지 보도가 있어야 합니다.
지도는 바다로 둘러싸여 있어 지도 밖으로 나갈 수 없습니다.
기입
입력은 여러 테스트 케이스로 구성됩니다.
각 테스트 케이스의 첫 번째 줄은 맵의 너비 w와 높이 h를 제공합니다.
w 및 h는 50 이하의 양의 정수입니다.
지도는 두 번째 행부터 h행으로 제공됩니다.
1은 육지, 0은 바다입니다.
입력의 마지막 줄에는 두 개의 0이 있습니다.
누르다
각 테스트 케이스의 섬 수를 출력하십시오.
설명
– DFS 사용
– 섬의 연결된 모든 위치를 방문한 후 새로운 섬을 탐색하는 방법
– 글로벌 기능으로 새로운 섬이 시작될 때마다 +1을 세세요.
– 방문한 장소는 다시 방문할 수 없도록 설정되어 있습니다.
import sys
di = (-1, -1, 0, 1, 1, 1, 0, -1)
dj = (0, 1, 1, 1, 0, -1, -1, -1)
def dfs(row, col):
global count
stack = ()
stack.append((row, col))
m(row)(col) = 0
if visited(row)(col) == 0:
visited(row)(col) = 1
count += 1
while stack:
row, col = stack.pop()
for k in range(8):
newR = row + di(k)
newC = col + dj(k)
if 0<= newR < h and 0<= newC < w and m(newR)(newC) == 1 and visited(newR)(newC) == 0:
visited(newR)(newC) = 1
m(newR)(newC) = 0
stack.append((newR, newC))
while True:
w, h = map(int, sys.stdin.readline().split())
if w == 0 and h == 0:
break
m = (list(map(int, sys.stdin.readline().split())) for _ in range(h))
visited = ((0)*w for _ in range(h))
count = 0
for i in range(h):
for j in range(w):
if m(i)(j) == 1:
dfs(i,j)
print(count)