トマト


質問する



コード#コード#

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**)

dx = [1,-1,0,0,1,1,-1,-1]
dy = [0,0,-1,1,1,-1,1,-1] #대각선 벡터도 추가 

def dfs(x,y):
  graph[x][y]=0 #방문 ! 
  for i in range(8):
      cx = x+dx[i]
      cy = y+dy[i]
      if 0<=cx<n  and 0<=cy<m and graph[cx][cy]==1:
        dfs(cx,cy)

while True :
    cnt=0
    m,n = map(int,input().split())
    if(m==n==0):
        break
    graph=[]

    for i in range(n):
        graph.append(list(map(int, input().rstrip().split()))) #입력받기 

    for j in range(n):
        for k in range(m):
            if (graph[j][k]==1):
                dfs(j,k)
                cnt+=1
    print(cnt)    

解説


以前の問題と似ているが,島の数を計算する際,BFSではなくDFSを用いてこれを実現した.
横ベクトルを生成するためにdx,dyに方向ベクトルを追加し,横ベクトルにナビゲートできるようにした.
そして1を0に変更して全島消滅で探索した.