import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def BFS():
cnt = 0
fuel = K
start = first
while True:
if cnt == M:
print(fuel)
return
visited = [[0]*N for i in range(N)]
dq = deque()
dq.append((*start,0))
distance = 1000
passenger = M+2
while dq:
y,x,d = dq.popleft()
if d>distance:
break
if d > fuel:
print(-1)
return
if visited[y][x]:
continue
visited[y][x] = 1
if board[y][x]:
passenger = min(passenger,board[y][x])
distance = d
continue
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and N>x1>=0:
if visited[y1][x1] or board[y1][x1]==1:
continue
dq.append((y1,x1,d+1))
if passenger == M+2:
print(-1)
return
fuel -= distance
ys,xs,ye,xe = startend[passenger]
board[ys][xs] = 0
f = taxi(ys,xs,ye,xe)
if f>fuel or f == -1:
print(-1)
return
start = (ye,xe)
fuel += f
cnt += 1
def taxi(ys,xs,ye,xe):
visited = [[0]*N for i in range(N)]
dq = deque()
dq.append((ys,xs,0))
while dq:
y,x,d = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = 1
if (y,x) == (ye,xe):
return d
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and N>x1>=0:
if visited[y1][x1] or board[y1][x1] == 1:
continue
dq.append((y1,x1,d+1))
return -1
N,M,K = map(int,input().split())
board = []
for i in range(N):
board.append([*map(int,input().split())])
first = tuple(map(lambda x:x-1,map(int,input().split())))
data = []
startend = {}
for i in range(M):
data.append([*map(lambda x:x-1,map(int,input().split()))])
data.sort()
for i in range(2,M+2):
y1,x1,y2,x2 = data[i-2]
board[y1][x1] = i
startend[i] = (y1,x1,y2,x2)
BFS()
아이디어는 쉬운데 반례잡기가 까다로울 수 있는 문제이다.
알고리즘만 설명하면,
1. 손님들의 데이터를 받아서 y,x 좌표가 작은 순으로 정렬해준다.
2. 손님들에게 2~M+1까지 번호를 매기고 각 손님들의 시작좌표를 해당 번호로 바꾼다. (1은 벽이므로)
3. 현재 위치에서 BFS로 가장 가까운 손님을 발견하면 distance를 갱신하고 번호는 작은 번호로 바꾸어준다.
4. 번호가 바뀐적이 없으면 -1을 출력
5. 바뀐적이 있으면 해당 번호 손님의 도착위치로 가는 거리를 BFS로 계산
6. 거리가 현재의 연료양보다 크면 -1 출력, 아니면 거리만큼 연료 +
7. 모든 손님을 태워주면 결과 출력
내가 실수한 부분은
1번에서 정렬을 하지 않고 데이터를 받는대로 번호를 매겼다.
4번의 번호가 바뀐적이 없으면 -1을 출력하지 않았다. (도착지점에 도달하지 못하면 -1을 출력하는건 처리해줬는데, 다음 손님을 발견 못하면 -1을 출력하지 않았다.)
오늘의 교훈) 항상 예외케이스를 염두하자