BOJ 4963島の数
9624 ワード
https://www.acmicpc.net/problem/4963
時間1秒、メモリ128 MB
input :の複数のテストケース. 幅w,高h(1<=w,h<=50) 1は地、0は海 で入力した最後の行に0を入力します. output :各試験盤キャビネットの島数出力. 条件:同じ島:1つの正方形から別の正方形(上下左右、対角線接続) 空のグラフィックをテスト、塗りつぶし、再塗りつぶします.
繰り返し文で入力を受信し続ける必要があります.
必要な変数
visitは1と0に分かればいいので不要です.
島の数を記録する島変数.
必要な関数
島の個数を計算する関数.
繰り返し文の内部で、2 Dリスト全体で島の開始部分を探します.
正しいコード:
最初はランタイムエラーが発生しましたが
sys.setrecursionlimit(10000)remitを設定して通過します.
忘れないで!
時間1秒、メモリ128 MB
input :
繰り返し文で入力を受信し続ける必要があります.
必要な変数
visitは1と0に分かればいいので不要です.
島の数を記録する島変数.
必要な関数
島の個数を計算する関数.
繰り返し文の内部で、2 Dリスト全体で島の開始部分を探します.
正しいコード:
import sys
sys.setrecursionlimit(10000)
w, h = map(int, sys.stdin.readline().split())
ans = []
def DFS(navi, position):
navi[position[0]][position[1]] = 0
dx = [1, -1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, 1, -1, -1, 1, -1, 1]
for i in range(len(dx)):
nx = position[0] + dx[i]
ny = position[1] + dy[i]
if nx >= h or nx < 0 or ny >= w or ny < 0:
continue
if navi[nx][ny]:
DFS(navi, [nx, ny])
while w != 0 and h != 0:
graph = []
cnt = 0
for i in range(h):
data = list(map(int, sys.stdin.readline().split()))
graph.append(data)
for x in range(h):
for y in range(w):
if graph[x][y]:
DFS(graph, [x, y])
cnt += 1
ans.append(cnt)
w, h = map(int, sys.stdin.readline().split())
for data in ans:
print(data)
最初はランタイムエラーが発生しましたが
sys.setrecursionlimit(10000)remitを設定して通過します.
忘れないで!
Reference
この問題について(BOJ 4963島の数), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/BOJ-4963-섬의-개수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol