악어

클라스는 호주 여행 중에 돈이 떨어져 가고 있었다. 다행히 그는 사람들의 정원에서 악어를 쫓아내는 아주 좋은 아르바이트를 찾았다. 첫 번째 일감은 $N \times M$ 격자로 표현되는 수영장이다. 각 칸은 비어 있거나 잠자고 있는 악어 한 마리를 담고 있다. 잠자고 있는 악어는 동서남북 중 한 방향을 향하고 있다. 클라스는 악어에게 사과를 던져 깨울 수 있다. 깨어난 악어는 향하고 있는 방향으로 매우 빠르게 헤엄치며, 수영장 밖으로 나가거나 다른 악어와 부딪칠 때까지 계속 움직인다. 두 악어가 부딪히면 둘 다 매우 화가 나고, 클라스를 공격할 위험이 크다.

클라스가 사과를 최적의 방식으로 던질 때, 수영장에서 몇 마리의 악어를 빼낼 수 있는지 구하여라. 두 악어가 부딪혀서는 안 된다. 클라스는 한 번에 사과를 하나만 던질 수 있고, 악어가 매우 빠르게 움직이므로 앞선 악어가 움직임을 마치기 전에는 다음 사과를 던질 수 없다.