[USACO Oct09]乳草的入侵

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file milkweed.in Output file milkweed.out

Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿,他在植
物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样,被分割成一个高度为Y(1 <= y <= 100), 宽度为X(1 <= x <= 100)的
直角网格。(1,1)是左下角的格(也就是说坐标排布跟一般的X,Y坐标相同)。乳草一开始占
领了格(Mx,My)。每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头
的格(包括垂直与水平相邻的和对角线上相邻的格)。1周之后,这些新占领的格又可以把乳草
传播到更多的格里面了。

Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才
能占领整个草地。如果乳草在0时刻处於格(Mx,My),那麼还在那个时刻它们可以完全占领入侵
整片草地呢(对给定的数据总是会发生)?

草地由一个图片表示。"."表示草,而"*"表示大石。比如这个X=4, Y=3的例子。

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

如果乳草一开始在左下角(第1排,第1列),那麼草地的地图将会以如下态势发展:

      .... .... MMM. MMMM MMMM
      ..*. MM*. MM*. MM*M MM*M
      M**. M**. M**. M**. M**M
星期数 0     1     2     3     4

乳草会在4星期后占领整片土地。

题目名称: milkweed

输入格式:

* 第一行: 四个由空格隔开的整数: X, Y, Mx, My

* 第2到第Y+1行: 数据的第y+1行由X个字符("."表示草地,"*"表示大石),描述草地的
    第(Y+2-y)行。

样例输入 (文件 milkweed.in):

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

输出格式:

* 第一行: 一个单独的整数表示最后一个不是大石块的格子被乳草占领的星期数。如果这永远
    不发生,输出-1.

样例输出 (文件 milkweed.out):

4