BOJ:2636チーズ
bfsを利用した.最初はエッジがdefault空気であることを知らず、エッジに空気が入っている部分を見つけ、
start
リストに入れてbfsを回したが失敗した.(0,0)だけ入れて、すぐに成功したのに、どうして、import sys
from collections import deque
# 치즈가 모두 녹아 없어지는 데 걸리는 시간과, 모두 녹기 한 시간 전에 치즈 조각이 놓여있는 칸의 개수를 구하자
sys.setrecursionlimit(11111)
def isCheeze(h, w):
if cheeze[h][w] == 1:
return True
return False
def bfs(group, day):
cheeze = set()
air = set()
for h, w in group:
global visit
visit[h][w] = day
for (i, j) in [(1,0),(-1,0),(0,1),(0,-1)]:
new_h, new_w = (h + i, w + j)
if 0 <= new_h < height and 0 <= new_w < width:
if isCheeze(new_h, new_w) and (visit[new_h][new_w] == -1 or visit[new_h][new_w] > day + 1):
cheeze.add((new_h, new_w))
elif not isCheeze(new_h, new_w) and (visit[new_h][new_w] == -1 or visit[new_h][new_w] > day):
air.add((new_h, new_w))
if air:
bfs(air, day)
if cheeze:
bfs(cheeze, day + 1)
input = sys.stdin.readline
height, width = list(map(int, list(input().strip().split())))
cheeze = [list(map(int, list(input().strip().split()))) for _ in range(height)]
# (x,y)좌표 cheeze => cheeze[y - 1][x - 1]
visit = [[-1] * width for _ in range(height)]
# 처음 가장자리 중 공기가 있는 부분 찾기
start = [(0,0)]
# for h in [0, height - 1]:
# for w in range(0, width):
# if not isCheeze(h, w):
# start.append((h, w))
# for w in [0, width - 1]:
# for h in range(0, height):
# if not isCheeze(h, w):
# start.append((h, w))
day = 0
bfs(start, day)
max = 0
max_count = 0
for h in range(height):
for w in range(width):
if visit[h][w] > max and isCheeze(h, w):
max = visit[h][w]
max_count = 1
elif visit[h][w] == max and isCheeze(h, w):
max_count += 1
print(max)
print(max_count)
Reference
この問題について(BOJ:2636チーズ), 我々は、より多くの情報をここで見つけました https://velog.io/@jujube0/BOJ-2636-치즈テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol