October 2009 Qualifying Invasion of the Milkweed乳草的入侵_题目

问题描述：(分值125)

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

草地被分割成一个高度为Y(1≤Y≤100), 宽度为X(1≤X≤100)的矩形网格。(1,1)是左下角的网格(同直角坐标)。乳草一开始占领了格(m x,m y)。每经过1个星期，乳草将传播与其相邻的没有大石头的草地上(包括垂直,水平,左右对角相邻的网格)。

Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才能占领整个草地。如果乳草在0时刻处于格(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

星期数 0 1 2 3 4

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

输入格式

第1行：4个整数由空格隔开的整数: X,Y,m x,m y。

第2..Y+1行: 第i+1行表示第i行草地由X个字符("."表示草地，"*"表示大石)。

输出格式

仅一行，一个整数：表示最后一个不是大石块的格子被乳草占领的星期数。

样例输入输出

milkweed.in

4 3 1 1

....

..*.

.**.

milkweed.out

4

- 1 –2010-04-09