던전 벽
시간 제한8초메모리 제한512 MB
내부 벽이 있는 격자에서 길이 1인 벽을 하나 추가해 입구에서 출구까지 최단 경로 길이의 증가분이 최대가 되도록 하되 경로가 남아 있어야 한다.
문제
2337년, 사람들은 지루한 일상에 싫증을 느끼고 비일상적인 경험을 갈망하게 되었다. 요즘 가장 인기 있는 명소 중 하나는 용감한 모험가들이 목숨을 걸고 사악한 몬스터를 처치하며 세계를 구하는 "던전 어드벤처"이다.
당신은 그런 던전 중 하나의 관리자이다. 최근 당신의 던전에 자주 들어오는 병사들로부터 불만이 쏟아지고 있다. 던전이 너무 쉽다며 다시는 들어가고 싶지 않다고 한다. 당신은 입구와 출구 사이의 거리를 늘려 더 많은 몬스터가 모험가에게 접근할 수 있도록 던전을 더 어렵게 만들려고 한다.
던전의 모양은 너비가 W, 높이가 H인 직사각형이다. 던전은 1 × 1 크기의 정사각형 방 W × H개로 이루어진 격자이다. 던전의 남서쪽 모서리 좌표는 (0, 0)이고 북동쪽 모서리 좌표는 (W, H)이다. 던전 외부는 벽으로 둘러싸여 있으며, 모험가가 출구로 곧장 가는 것을 막기 위해 던전 내부에도 벽이 있을 수 있다. 던전의 각 벽은 x축 또는 y축에 평행하고, 각 벽의 양 끝은 정수 좌표에 있다. 모험가는 두 방이 세로 또는 가로로 인접하고 그 사이에 벽이 없으면 한 방에서 다른 방으로 이동할 수 있다.
당신은 벽을 몇 개 추가해 입구와 출구 사이의 최단 경로를 더 길게 만들고 싶다. 그러나 심각한 재정 상황 때문에 길이가 1인 벽을 많아야 하나만 지을 수 있다. 새로 짓는 벽도 위에 서술한 제약을 따라야 한다. 또한 입구에서 출구까지 가는 경로가 적어도 하나는 있어야 한다.
입구와 출구 사이의 최소 이동 횟수를 최대로 만들려면 새 벽을 어디에 두어야 할지 고민하고 있다. 알아낼 수 있겠는가?
입력
W H N
sx0 sy0 dx0 dy0
sx1 sy1 dx1 dy1
.
.
.
ix iy
ox oy
첫째 줄에 세 정수 W, H, N이 공백으로 구분되어 주어진다. (1 ≤ W, H ≤ 50, 0 ≤ N ≤ 1000)
다음 N개 줄에는 던전 내부의 벽 N개의 정보가 주어진다. 각 벽의 정보는 네 정수로 이루어진 한 줄이다. i번째 정보에는 sxi, syi, dxi, dyi가 공백으로 구분되어 주어진다. 이 정수들은 i번째 벽의 위치를 나타내며, 벽은 (sxi, syi)에서 (dxi, dyi)까지 이어진다.
마지막 두 줄에는 입구와 출구의 위치 정보가 주어진다. 첫째 줄에는 두 정수 ix, iy가, 둘째 줄에는 두 정수 ox, oy가 주어진다. 입구는 남서쪽 모서리가 (ix, iy)인 방에 있고, 출구는 남서쪽 모서리가 (ox, oy)인 방에 있다.
출력
벽을 하나만 추가해서 얻을 수 있는 입구와 출구 사이의 최소 이동 횟수의 최대 증가량을 출력한다. 새 벽을 지을 만한 곳이 없으면 0을 출력한다.