HZNUOJ

WA Jiana的面包

Tags:   BFS  坑题  输入巨坑
Time Limit:  1 s      Memory Limit:   128 MB
Submission:465     AC:139     Score:92.38

Description

WA Jiana都已经188了,但是她还是一直吃吃吃。而且她时常把东西藏起来,害怕被别人抢了。有一次她藏了一块面包,由于藏的太好,自己都忘记吃了,当她找到面包时,发现有一个小区域已经发霉了。她伤心极了,就在旁边哭了好久好久,当她哭完后,发现整块面包都已经布满了霉菌。

假设面包被分割成一个高度为Y(1≤y≤100),宽度为X(1x100)的直角网格。(1,1)是左下角的格(也就是说坐标排布跟一般的X,Y坐标相同)。霉菌一开始占领了格(Mx,My)。每过一天,已被占领的格子里的霉菌会传播到周围每一个有面包的格子里(包括垂直与水平相邻的和对角线上相邻的格子)。一天之后,这些新占领的格子又可以把霉菌传播到更多的格子里面。 

WA Jiana想要知道自己至少哭了多少天?

面包由一个图片表示。" ." 表示有面包,而" *" 表示没有面包。

比如这个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天后占领整个面包。

Input

对于每组输入:

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

接下来是一个X列Y行的网格(" ." 表示有面包,而" *" 表示没有面包)。

Output

一个单独的整数表示最后一个有面包的格子被霉菌占领所需的天数。

Samples

input
4 3 1 1 .... ..*. .**.
output
4

Author

ZHOU, Zhao