밀크위드 timer 1초 memory 128MB

밀크위드(Milk Weed)는 우유맛이 나는 잔디로 소들의 사랑을 받는 잔디이며, 이런 밀크위드가 목초지에 자라고 있는 상황이다.

목초지는 높이 Y와 너비 X로 이루어진 직사각형 그리드로 나누어져 있으며, (1,1)은 좌측 하단에 위치한다.

밀크위드는 처음에 (M_x, M_y) 지점에서 자라기 시작한다. 매주 밀크위드는 이미 자란 칸을 둘러싼 모든 바위가 아닌 칸으로 퍼져 나간다. 이때 주변의 최대 8개 칸(직선 방향과 대각선 방향 모두)을 포함하여 확산된다. 그 칸들에서 일주일이 지나면, 밀크위드는 더 많은 칸으로 퍼져 나갈 준비가 된다.

베시(Bessie)는 밀크위드가 목초지를 완전히 덮어버리기 전에 풀을 최대한 즐기고 싶어 한다. 그녀는 밀크위드가 얼마나 시간이 지나야 마지막 풀밭을 모두 차지하는지 궁금해 한다. 밀크위드가 (M_x, M_y) 지점에서 시작될 때, 이 목초지가 완전히 침입당하는 주를 구하라 (주어진 입력에서는 항상 침입이 완료된다고 보장된다).

목초지는 다음과 같은 형태로 주어진다: .은 풀, *은 바위를 나타낸다. 예를 들어, X=4,\ Y=3일 때의 목초지는 다음과 같다:

 ....
 ..*.
 .**.

밀크위드가 (1, 1)에서 시작하면, 이 지도는 다음과 같이 진행된다:

 ....  ....  MMM.  MMMM  MMMM
 ..*.  MM*.  MM*.  MM*M  MM*M
 M**.  M**.  M**.  M**.  M**M

밀크위드는 4주 만에 전체 필드를 차지한다.