1297 问题 D: 乳草的入侵

 时间限制: 1s 内存限制: 128MB
题目描述

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星期后占领整片土地。

输入

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

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

输出
第一行：一个单独的整数表示最后一个不是大石块的格子被乳草占领的星期数。

样例输入

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

样例输出

4
提示
零基础同学可以先学习视频课程，包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程，提供视频讲解以及配套习题，还有老师答疑，点击这里了解课程详情

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            水水水！！！                        

                    

                

                

                    

                        
比赛状况