경찰차 (Tiny) (KOISTUDY 2146)

문제

N×N 격자에서 경찰차 1은 (1, 1), 경찰차 2는 (N, N)에서 시작한다. 사건 W개를 입력 순서대로 처리한다. 사건마다 두 차 중 한 대만 사건 위치로 이동하며, 처리 후 그 위치에서 기다린다. 상하좌우로 한 칸 이동하는 거리는 1이다. 두 차의 총 이동 거리의 최솟값을 구한다.

KOISTUDY 2146 원문을 바탕으로 정리한 실습 문제이다.

제한

5 ≤ N ≤ 20, 1 ≤ W ≤ 12. 각 사건의 행과 열은 1 이상 N 이하이다.

입출력 예시

예제 1 입력

6
3
3 5
5 5
2 3

예제 1 출력

9

예제 2 입력

5
1
1 1

예제 2 출력

0

예제 3 입력

5
2
1 1
5 5

예제 3 출력

0