당신의 회사는 청소용 로봇을 공급한다. 청소 로봇들이 필드에 투입되기 전에 먼저 필드의 사진이 주어진다.

이 사진은 격자 이미지로 각 칸에는 쓰레기가 있는지 여부가 표시되어 있다.

모든 로봇들은 (1,1) 위치에서 출발하여 오른쪽 또는 아래쪽 방향으로만 이동할 수 있다.

로봇이 지나간 자리는 청소가 된다.

한번 로봇이 (1,1)의 반대편 꼭지점에 도달하면 이 로봇은 다시 사용되지 않는다. 현재 필드의 쓰레기 분포가 주어졌을 때, 최소 몇 대의 로봇을 투입해야 하는지 알아내자.

그림1과 같은 필드가 주어졌다고 할 때, 그림2는 가능한 해법 의 예이다.

청소로봇 timer 1s memory - MB

청소로봇 1s - MB