# 택시에서 가장 가까운 손님부터 태움(여러개면 행이 작은 손님부터)
# 택시가 한 칸 움직일때마다 연료는 1씩 감소
# 택시가 승객에게 가는 데 연료 소모되고, 목적지까지 가는데 연료 소모됨
# 택시가 목적지에 도달하면 승객이 탄 시점부터 목적지까지 가는데 사용한 연료의 두배만큼 충전됨
# 택시가 가다가 중간에 연료를 다쓰면 종료 (도착지에 도착하면서 다쓴건 종료 아님)
# 모든 승객을 데려다줄 수 있는지? 가능하면 마지막에 남은 연료 양 출력하기
import sys
from collections import deque
input = sys.stdin.readline
line = list(map(int, input().split()))
n, m, fuel = line[0], line[1], line[2]
maps = [] # 0: 빈공간, 1: 벽, 2: 승객
for i in range(0, n):
lines = list(map(int, input().split()))
maps.append(lines)
taxi_x, taxi_y = map(int, input().split())
taxi_x -= 1
taxi_y -= 1
user_list = {} # 승객별 목적지 저장 딕셔너리(키: 승객 좌표, 값: 목적지 좌표)
for i in range(0, m):
lines = list(map(int, input().split()))
start_x, start_y = lines[0] - 1, lines[1] - 1
maps[start_x][start_y] = 2
user_list[(start_x, start_y)] = [lines[2] - 1, lines[3] - 1]
# 상, 좌 부터 탐색하도록 함 (거리 상 가까운 승객이 둘이면 행, 열이 작은 손님부터 태워야하므로)
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 택시 운행 스타트
def go_to_destination(maps, x, y):
visited = []
for j in range(n):
visited.append([False] * n)
visited[x][y] = True
dest_x, dest_y = user_list[(x, y)]
queue = deque([(x, y, 0)])
while queue:
x, y, dist = queue.popleft()
# 목적지 도착하면 현재 거리 리턴(bfs는 최단거리 보장되므로)
if x == dest_x and y == dest_y:
return dist
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 가고자 하는 곳이 맵 내부고, 벽이 아니고, 방문한 곳이 아니라면
if (
0 <= nx < n
and 0 <= ny < n
and maps[nx][ny] != 1
and not visited[nx][ny]
):
visited[nx][ny] = True
queue.append((nx, ny, dist + 1))
return -1
# bfs로 현재 택시로부터 가장 가까운 위치의 승객을 찾기 (소요되는 연료도 구하기)
def find_user(maps, x, y):
if maps[x][y] == 2:
return 0, x, y
visited = []
for j in range(n):
visited.append([False] * n)
visited[x][y] = True
candidates = []
min_dist = -1 # 찾은 최소 거리
queue = deque([(x, y, 0)])
while queue:
x, y, dist = queue.popleft()
# 이미 승객을 찾았고, 그 최소 거리보다 거리가 더 커지면 더 볼 필요 없으므로 종료
# if min_dist != -1 and dist >= min_dist:
# break
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
# 가고자 하는 곳이 맵 내부고, 벽이 아니고, 방문한 곳이 아니라면
if (
0 <= nx < n
and 0 <= ny < n
and maps[nx][ny] != 1
and not visited[nx][ny]
):
visited[nx][ny] = True
# 승객을 찾았다면
if maps[nx][ny] == 2:
# 거리는 한 칸 더 가야 승객 위치이므로 + 1
candidates.append([dist + 1, nx, ny])
min_dist = dist + 1
# 여기서 찾았다고 break 하지 않기! 거리가 동일한 다른 손님도 찾아야 하므로
else:
queue.append((nx, ny, dist + 1))
if candidates:
candidates.sort()
# 승객에게 도달할 수 없다면
else:
return -1, -1, -1
# 가장 가까운 승객의 좌표 및 거리 리턴
return candidates[0][0], candidates[0][1], candidates[0][2]
all_clear = True
# 모든 승객에 대해서
for i in range(0, m):
# 현재 위치에서 가장 가까운 승객 찾기
dist, user_x, user_y = find_user(maps, taxi_x, taxi_y)
if user_x == -1 and user_y == -1:
all_clear = False
break
# 현재 연료로 갈 수 있다면, 승객 위치로 택시 이동, 거리만큼 연료 소모
if fuel >= dist:
taxi_x, taxi_y = user_x, user_y
fuel -= dist
# 승객 태워서 목적지까지 이동할 수 있는지 체크
min_dist = go_to_destination(maps, taxi_x, taxi_y)
# -1 예외처리
if min_dist == -1:
all_clear = False
break
# 목적지까지 이동 가능하면
if fuel >= min_dist:
# 승객 태워서
maps[taxi_x][taxi_y] = 0
# 택시를 목적지로 위치 이동
dest_x, dest_y = user_list[(taxi_x, taxi_y)]
taxi_x, taxi_y = dest_x, dest_y
del user_list[(user_x, user_y)]
# 연료 소모
fuel -= min_dist
# 택시가 목적지에 도달하면 승객이 탄 시점부터 목적지까지 가는데 사용한 연료의 두배만큼 충전됨
fuel += min_dist * 2
else:
all_clear = False
break
else:
all_clear = False
break
if not all_clear:
print("-1")
else:
print(fuel)
