安全区域(BFS、DFS)
19485 ワード
作成日:2022年2月18日午後3:03
の最良の答えの中で、私はDFSを使って、私はBFSを使って を実現しますウェブサイト(バージンなど)で問題や採点に時間遅延エラーが発生した場合、
インプリメンテーションコード
# 안전영역 (BFS)
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
sys.setrecursionlimit(10**6)
def BFS(L):
global res
cnt = 0
Q = deque()
ch = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] <= L:
ch[i][j] = 1
for i in range(n):
for j in range(n):
if ch[i][j] == 0:
ch[i][j] = 1
Q.append((i,j))
cnt += 1
while Q:
tmp = Q.popleft()
for k in range(4):
x = tmp[0]+dx[k]
y = tmp[1]+dy[k]
if 0<=x<n and 0<=y<n and ch[x][y] == 0:
ch[x][y] = 1
Q.append((x,y))
if cnt > res:
res = cnt
if __name__ == "__main__":
n = int(input())
board = []
max = -2147000000
for i in range(n):
tmp = list(map(int, input().split()))
for j in range(n):
if tmp[j] > max:
max = tmp[j]
board.append(tmp)
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
res = 0
for i in range(1, max):
BFS(i)
print(res)
模範解答
import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
sys.setrecursionlimit(10**6)
def DFS(x, y, h):
ch[x][y]=1
for i in range(4):
xx=x+dx[i]
yy=y+dy[i]
if 0<=xx<n and 0<=yy<n and ch[xx][yy]==0 and board[xx][yy]>h:
DFS(xx, yy, h)
if __name__=="__main__":
n = int(input())
cnt = 0
res = 0
board=[list(map(int, input().split())) for _ in range(n)]
for h in range(100):
ch=[[0]*n for _ in range(n)]
cnt=0
for i in range(n):
for j in range(n):
if ch[i][j]==0 and board[i][j]>h:
cnt+=1
DFS(i, j, h)
res=max(res, cnt)
if cnt==0:
break
print(res)
差異
sys.setrecursionlimit(10**6)
はコードを追加することで解決できます.Reference
この問題について(安全区域(BFS、DFS)), 我々は、より多くの情報をここで見つけました https://velog.io/@lsj8706/안전영역-BFS-DFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol