백준 19238 스타트택시

from collections import deque
import sys
input = sys.stdin.readline
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m, gas = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
c_list = []
for _ in range(m):
    fx, fy, tx, ty = map(int, input().split())
    c_list.append((fx - 1, fy - 1, tx - 1, ty - 1))
c_list.sort(reverse=True)

def bfs(sx, sy):
    tmp = [[-1] * n for _ in range(n)]
    q = deque()
    q.append((sx, sy))
    tmp[sx][sy] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if g[nx][ny] == 0 and tmp[nx][ny] == -1:
                tmp[nx][ny] = tmp[x][y] + 1
                q.append((nx, ny))
    return tmp

ans = 0
while ans < m:
    check = bfs(sx, sy)
    init = n * n + 1
    for fx, fy, tx, ty in c_list:
        if init >= check[fx][fy]:
            ffx, ffy, ttx, tty = fx, fy, tx, ty
            init = check[fx][fy]
    c_list.remove((ffx, ffy, ttx, tty))
    gas -= check[ffx][ffy]
    if gas < 0 or check[fx][fy] == -1 or check[ffx][ffy] == -1:
        gas = -1
        break
    check = bfs(ffx, ffy)
    gas -= check[ttx][tty]
    if gas < 0:
        gas = -1
        break
    gas += 2 * check[ttx][tty]
    sx, sy = ttx, tty
    if check[ttx][tty] == -1:
        gas = -1
        break
    ans += 1

print(gas)