🔥

문제

민기는 사라진 고양이를 구하기 위해 숲 속으로 들어갔다. 숲은 (N, M) 크기의 격자로 표현되며, 입구는 (1, 1)에 있고 고양이는 (N, M)에 위치해있다. 민기는 상하좌우로 이동할 수 있고, 한 칸을 이동하는데 1분이 걸린다.

숲에는 나무로 이루어진 격자가 있고, 민기는 이를 통과할 수 없다. 하지만, 숲 속에 도끼를 주으면 앞을 가로막는 나무를 단숨에 베어낼 수 있다. 도끼는 숲 속에 단 하나 존재한다.

고양이는 인내심에 한계가 있기 때문에, 주인을 T분만 기다린다. 만약 T분 동안 고양이가 있는 칸에 도달하지 못하면 고양이는 영영 도망쳐버린다.

민기가 고양이를 구할 있는지, 구하려면 얼마의 시간이 필요한지 구하여라

입력

첫 번째 줄에는 숲의 가로, 세로의 길이인 N, M 그리고 고양이가 기다려주는 시간 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 숲의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 나무, 2는 도끼가 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

출력

고양이를 구하기 위해서는 최소 몇 분이 걸리는지 출력하여라. 만약 고양이를 구할 수 없다면 Fail을 출력하여라

예제 1 입력

6 6 16
0 0 0 0 1 1
0 0 0 0 0 2
1 1 1 0 1 0
0 0 0 0 0 1
0 1 1 1 1 1
0 0 0 0 0 0

예제 1 출력

10

예제 2 입력

3 4 100
0 0 0 0
1 1 1 1
0 0 2 0

예제 2 출력

Fail

Source

from collections import deque

n, m, t = map(int, input().split())
forest = [list(map(int, input().split())) for _ in range(n)]
dist = [[[0 for _ in range(2)] for _ in range(m + 1)] for _ in range(n + 1)]

q = deque()
q.append([0, 0, 0, 1])

while(len(q)):
	x, y, z, d = q.popleft()

	if(x < 0 or y < 0 or x >= n or y >= m):
		continue
	if(forest[x][y] == 2):
		z = 1
	if(forest[x][y] == 1 and z == 0):
		continue
	if(dist[x][y][z] > 0):
		continue

	dist[x][y][z] = d

	dx = [-1, 0, 1, 0]
	dy = [0, -1, 0, 1]

	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		q.append([nx, ny, z, d + 1])

ans = n * m + 1
if(dist[n - 1][m - 1][0] > 0):
	ans = min(ans, dist[n - 1][m - 1][0] - 1)
if(dist[n - 1][m - 1][1] > 0):
	ans = min(ans, dist[n - 1][m - 1][1] - 1)

if(ans == n * m + 1 or ans > t):
	print("Fail")
else:
	print(ans)

참고