トマト
質問する
コード#コード# 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に変更して全島消滅で探索した.
Reference
この問題について(トマト), 我々は、より多くの情報をここで見つけました
https://velog.io/@seochan99/7576-토마토-ezahn7l1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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に変更して全島消滅で探索した.
Reference
この問題について(トマト), 我々は、より多くの情報をここで見つけました
https://velog.io/@seochan99/7576-토마토-ezahn7l1
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Reference
この問題について(トマト), 我々は、より多くの情報をここで見つけました https://velog.io/@seochan99/7576-토마토-ezahn7l1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol