시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 29 2 2 33.333%

문제

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

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

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

입력

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

출력

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

예제 입력

0 0
99 0
0 99

예제 출력

1

힌트

출처