当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1454:乳草的入侵

题目描述
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列),那麼草地的地图将会以如下态势发展:



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

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

* 第2到第Y+1行: 数据的第y+1行由X个字符("."表示草地,"*"表示大石),描述草地的
第(Y+2-y)行。
输出解释
* 第一行: 一个单独的整数表示最后一个不是大石块的格子被乳草佔领的星期数。
输入样例
4 3 1 1
....
..*.
.**.
输出样例
4
提示
各个测试点1s


广度优先搜索


该题目包含在题集 ACM赛制

题目来源 USACO OCT09 6TH

共提交 42

通过率 35.71%
时间上限 内存上限
1000 MS 128 MB