스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
from collections import deque
n, m, gas = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
taxi_i, taxi_j = map(int, input().split())
taxi_i -= 1
taxi_j -= 1
start = []
end = []
for _ in range(m):
a, b, c, d = map(int, input().split())
start.append((a-1, b-1))
end.append((c-1, d-1))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
#도착한 고객을 확인하는 배열
suc = [0]*m
#가장 가까운 승객을 찾는 함수
def find():
visit = [[-1]*n for _ in range(n)]
queue = deque([(taxi_i, taxi_j)])
visit[taxi_i][taxi_j] = 1
while queue:
r, c = queue.popleft()
for k in range(4):
nx = r + dx[k]
ny = c + dy[k]
if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0 and visit[nx][ny] == -1:
visit[nx][ny] = visit[r][c] + 1
queue.append((nx, ny))
#태울 승객의 위치를 담을 변수
cus_x, cus_y = -1, -1
customer_num = 0
distance = n**2
for i in range(m):
if suc[i] == 0:
x, y = start[i]
if visit[x][y] == -1: #벽 때문에 목적지로 못가는 경우
return -1, -1, -1, -1
if visit[x][y] < distance:
cus_x = x
cus_y = y
customer_num = i
distance = visit[x][y]
elif visit[x][y] == distance:
if x < cus_x:
cus_x = x
cus_y = y
customer_num = i
distance = visit[x][y]
elif x == cus_x:
if y < cus_y:
cus_x = x
cus_y = y
customer_num = i
distance = visit[x][y]
return customer_num, cus_x, cus_y, distance-1 #탑승한 승객의 번호와 지금가지 이동한 거리를 리턴
#목적지로 승객을 데려다주는 함수
def go(customer_num):
dist_x, dist_y = end[customer_num]
# print(dist_x, dist_y)
visit = [[-1]*n for _ in range(n)]
queue = deque([(taxi_i, taxi_j)])
visit[taxi_i][taxi_j] = 1
while queue:
r, c = queue.popleft()
for k in range(4):
nx = r + dx[k]
ny = c + dy[k]
if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0 and visit[nx][ny] == -1:
visit[nx][ny] = visit[r][c] + 1
queue.append((nx, ny))
distance = visit[dist_x][dist_y]
return dist_x, dist_y, distance-1
cnt = 0
while True:
num, x, y, dis = find()
taxi_i = x
taxi_j = y
if num == -1 or gas - dis < 0: #데리러 갈 수 없거나 연료가 바닥난다면
print(-1)
break
gas -= dis
x, y, dis = go(num)
if gas - dis < 0:
print(-1)
break
gas -= dis
gas += dis*2
cnt+=1
suc[num] = 1
taxi_i = x
taxi_j = y
if cnt == m:
print(gas)
break