乳草入侵

题目描述

农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

可惜天不从人愿，他在植物大战人类中败下阵来。

邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地网格

草地被分割成一个高度为 $Y$，宽度为 $X$ 的直角网格。

注意坐标系统： $(1,1)$ 是左下角的格子（也就是说坐标排布跟一般的 $X,Y$ 坐标相同）。

乳草传播规则

乳草一开始占领了格子 $(M_x, M_y)$。

每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有石头的格子（包括垂直与水平相邻的和对角线上相邻的格子）内。

1 周之后，这些新占领的格子又可以把乳草传播到更多的格里面了。

问题

达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

她很好奇到底乳草要多久才能占领整个草地。

如果乳草在 $0$ 时刻处于格子 $(M_x, M_y)$，那么几个星期以后它们可以完全占领入侵整片草地呢（对给定的数据总是会发生）？

地图表示

在草地地图中：

• . 表示草地（可以被乳草占领）
• * 表示大石（乳草无法占领）

输入格式

第 1 行：四个由空格隔开的整数: $X$, $Y$, $M_x$, $M_y$

第 2 到第 $Y+1$ 行：每行包含一个由 $X$ 个字符（. 表示草地，* 表示大石）构成的字符串，共同描绘了草地的完整地图。

注意： 输入的地图行是从上到下给出的，但坐标系统是 $(1,1)$ 在左下角。

输出格式

输出一个整数，表示乳草完全占领草地所需要的星期数。

数据范围

$1 \le X, Y \le 100$

输入样例

4 3 1 1
....
..*.
.**.

输出样例

4

样例解释

草地尺寸：$X=4$（宽），$Y=3$（高）

初始乳草位置：$(M_x=1, M_y=1)$，即左下角格子

地图（输入顺序从上到下）：

第1行：....  (对应网格的y=3)
第2行：..*.  (对应网格的y=2)  
第3行：.**.  (对应网格的y=1)

坐标对应关系（左下角为(1,1)）：

(1,3) (2,3) (3,3) (4,3)  ->  ....
(1,2) (2,2) (3,2) (4,2)  ->  ..*.
(1,1) (2,1) (3,1) (4,1)  ->  .**.

乳草传播过程：

第0周：
....
..*.
M**.

第1周：
....
MM*.
M**.

第2周：
MMM.
MM*.
M**.

第3周：
MMM.
MM*M
M**.

第4周：
MMMM
MM*M
M**M

乳草在第4周后占领了所有可到达的草地格子（除了石头格子*）。

传播方向

乳草每周向8个方向传播：

• 上、下、左、右（垂直与水平）
• 左上、右上、左下、右下（对角线）

时空限制

• 时间限制：1秒
• 空间限制：64MB