P2960 [USACO09OCT] Invasion of the Milkweed G

农夫约翰一直尽力保持牧场里长满丰盛、美味且健康的草供奶牛食用。然而，他输掉了这场战斗，因为邪恶的乳草在他的农场西北部站稳了脚跟。 牧场通常被划分为一个直角网格，高度为 $Y$（$1 \le Y \le 100$），宽度为 $X$（$1 \le X \le 100$），其中 $(1,1)$ 位于左下角（即，排列为正常的 $X,Y$ 坐标网格）。乳草最初开始在方格 $(M_x,M_y)$ 生长。每周，乳草会传播到它已经占据的任何方格周围的所有非岩石方格，最多可以传播到八个方格（包括直角方格和对角线方格）。在这些方格中仅仅一周后，它就准备好继续传播到更多方格。 贝茜想在牧场被乳草占领之前尽可能多地享受青草。她想知道牧场能持续多久。如果乳草在时间零时位于方格 $(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 week 0 1 2 3 4 ``` 乳草在 4 周后占领了整个牧场。

\* 第 1 行：四个以空格分隔的整数：$X$，$Y$，$M_x$ 和 $M_y$ \* 第 2 行到第 $Y+1$ 行：第 $y+1$ 行描述了牧场的第 $(Y+2-y)$ 行，其中包含 $X$ 个字符（'.' 代表草，'\*' 代表巨石）

\* 第 1 行：一个整数，表示乳草占领牧场最后一个非巨石方格的周数。

（由 ChatGPT 4o 翻译）