스타트 택시

• 그냥 시키는 대로 구현하면 된다. 최단거리를 구해야 할때 BFS를 사용하면 된다.
• 풀이 자체는 어렵지 않지만, 구현이 길고 문제에 실수할만한 요소들도 많은, 짜증나는 유형..
• 구현이 긴 것은, 승객을 찾으러 가는 BFS와, 목적지를 찾으러 가는 BFS의 두가지를 모두 구현해야 하기 때문.
• 실수하기 쉬운 것은.. A 승객의 도착지가 B승객의 출발지일 수도 있다는 점, 출발지에서 도착지까지 갈수 있는 경로가 없을 수도 있다는 점 등이다..
• BFS 한번에 걸리는 시간은 O(N*N)이고, 승객 한명당 BFS 2번이 필요하다. 그래서 최종적으로 걸리는 시간은 O(N*N*M).

"""Solution code for "BOJ 19238. 스타트 택시".

- Problem link: https://www.acmicpc.net/problem/19238
- Solution link: http://www.teferi.net/ps/problems/boj/19238
"""

import collections
from typing import Callable, Generator, Iterable, List, Optional, Sequence, Tuple, TypeVar
T = TypeVar('T')
CellType = TypeVar('CellType')
PosType = Tuple[int, int]


INF = float('inf')


def bfs(start: T,
        get_next: Callable[[T], Iterable[T]]) -> Generator[T, None, None]:
    """Yields (node, distance) pairs for nodes in BFS-order."""
    yield (start, 0)
    visited = set()
    queue = collections.deque([(start, 0)])
    while queue:
        cur, dist = queue.popleft()
        for next_ in get_next(cur):
            if next_ not in visited:
                visited.add(next_)
                queue.append((next_, dist + 1))
                yield (next_, dist + 1)


def min_dist_targets(source: T,
                     get_next: Callable[[T], Iterable[T]],
                     is_target: Callable[[T], bool],
                     limit: Optional[int]) -> Tuple[List[T], Optional[int]]:
    targets = []
    for pos, dist in bfs(source, get_next):
        if limit and dist > limit:
            break
        if is_target(pos):
            targets.append(pos)
            limit = dist
    return (targets, limit)


def get_neighbors_from_grid(
    grid: Sequence[Sequence[CellType]],
    empty: CellType
) -> Callable[[PosType], Generator[PosType, None, None]]:
    """Returns a generator that yields neighbor cells in the grid."""
    row_count, col_count = len(grid), len(grid[0])

    def get_neighbors(pos):
        r, c = pos
        for dr, dc in ((-1, 0), (0, -1), (0, 1), (1, 0)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < row_count
                and 0 <= nc < col_count
                    and grid[nr][nc] == empty):
                yield (nr, nc)
    return get_neighbors


def main():
    N, M, fuel = [int(x) for x in input().split()]
    grid = []
    for _ in range(N):
        grid.append([int(x) for x in input().split()])
    cur_row, cur_col = [int(x) for x in input().split()]
    passengers = {}
    for _ in range(M):
        r1, c1, r2, c2 = [int(x) for x in input().split()]
        passengers[(r1 - 1, c1 - 1)] = ((r1 - 1, c1 - 1), (r2 - 1, c2 - 1))

    get_next_fn = get_neighbors_from_grid(grid, empty=0)
    source = (cur_row - 1, cur_col - 1)
    for _ in range(M):
        targets, dist = min_dist_targets(
            source, get_next_fn, lambda pos: pos in passengers, fuel)
        if not targets:
            print(-1)
            break
        fuel -= dist
        pos = min(targets)
        source, sink = passengers[pos]
        del passengers[pos]

        targets, dist = min_dist_targets(
            source, get_next_fn, lambda pos: pos == sink, fuel)
        if not targets:
            print(-1)
            break
        fuel += dist
        source = sink
    else:
        print(fuel)


if __name__ == '__main__':
    main()