1232번 - 체스

흰색 퀸과 두 검정색 킹이 100×100크기의 체스 판에 있다. 흰색과 검정색은 서로 턴을 번갈아 가면서 움직인다. 흰색 퀸이 먼저 움직인다. 검정색 킹의 턴에서는 두 검정 킹 중 하나만 움직인다.

퀸의 위치와 두 킹의 위치가 주어질 때, 두 킹 중 하나를 잡기 위해 필요한 퀸 움직임의 최솟값을 구하는 프로그램을 작성하시오. 킹은 퀸을 잡을 수 없으며, 퀸의 위치로 움직일 수도 없다.

검정 편은 가능하면 늦게 잡히려고 노력할 것이다. 킹은 상하좌우, 대각선 8방향으로 한 칸씩 이동할 수 있고, 퀸은 8방향으로 원하는 칸만큼 이동할 수 있다. 퀸이 킹이 있는 칸으로 이동하는 것이 킹을 잡는 것이고, 양 편 모두 턴을 건너 뛸 수 없으며, 체스 판을 벗어날 수 없다.

첫째 줄에 퀸의 위치, 둘째 줄과 셋째 줄에 킹의 위치가 주어진다. 모든 위치는 “행 열”과 같은 형식을 주어진다. (가장 왼쪽 위에 있는 칸이 (0, 0)이고, 가장 오른족 아래에 있는 칸이 (99, 99)이다. 퀸과 킹, 또는 두 킹이 같은 위치에 있는 경우는 없다.

첫째 줄에 킹을 잡기 위한 퀸의 움직임의 최솟값을 출력한다.