로봇

당신의 회사는 스포츠 경기나 콘서트가 끝난 뒤 경기장에 남은 쓰레기를 줍는 로봇을 제공한다. 로봇을 투입하기 전에, 경기장을 위에서 찍은 항공 사진 위에 격자를 씌우고 쓰레기가 있는 칸을 모두 표시한다. 모든 로봇은 북서쪽(왼쪽 위) 모서리에서 출발하여 남동쪽(오른쪽 아래) 모서리에서 이동을 마친다. 로봇은 동쪽 또는 남쪽, 두 방향으로만 이동할 수 있다. 쓰레기가 있는 칸에 들어가면 로봇은 그 쓰레기를 주운 뒤 계속 이동한다. 로봇이 남동쪽 모서리에 도착하면 다시 위치를 바꾸거나 재사용할 수 없다. 비용은 한 작업에 사용한 로봇의 수에 정비례하므로, 주어진 경기장을 청소하는 데 필요한 로봇의 최소 개수를 구하려고 한다.

예를 들어 그림 1의 경기장 지도를 보자. 행과 열에는 그림과 같이 번호가 매겨져 있고, 쓰레기가 있는 칸은 'G'로 표시되어 있다. 이 방식에서 모든 로봇은 (1, 1) 위치에서 출발하여 (6, 7) 위치에서 끝난다.

그림 1 - 경기장 지도

그림 2는 두 가지 가능한 해를 보여 준다. 두 번째 해가 로봇 세 대가 아니라 두 대만 사용하므로 더 낫다.

그림 2 - 두 가지 가능한 해

경기장의 모든 쓰레기를 줍는 데 필요한 로봇의 최소 개수를 구하는 프로그램을 작성하라.

입력은 하나 이상의 경기장 지도로 이루어지며, 마지막에 입력의 끝을 알리는 -1 -1이 적힌 줄이 온다. 각 경기장 지도는 한 줄에 하나씩 쓰레기 위치가 적힌 한 줄 이상으로 이루어지고, 그 뒤에 지도의 끝을 알리는 0 0이 적힌 줄이 온다. 각 쓰레기 위치는 행과 열을 나타내는 두 정수로 주어지며, 두 수는 공백 하나로 구분된다. 행과 열의 번호는 그림 1과 같다. 쓰레기 위치는 행 우선(row-major) 순서로 주어진다. 한 경기장 지도의 크기는 24행, 24열을 넘지 않는다.

각 경기장 지도마다, 그 경기장을 청소하는 데 필요한 로봇의 최소 개수를 한 줄에 출력한다.