#2816. 乳草的入侵

乳草的入侵

题目描述

约翰一直努力让他的草地充满鲜美多汁的而又香的牧草,可惜天不从人愿,他在植物大战人类中败下阵来.邪恶的乳草已经在他的农场的西北部份占领了一片立足之地.草地像往常 一样,被分割成一个高度为Y(1\red{Y(1≤}Y\red{Y≤}100),\red{100),}宽度为X(1\red{X(1≤}x\red{x≤}100)\red{100)}的直角网格.(1,1)\red{(1,1)}是左下角的格.

乳草一开始占领了格(Mx,My).\red{(M_x,M_y).}每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角在线相邻的格).

1\red{1}周之后,这些新占领的格又可以把乳草传播到更多的格里面了.贝茜想要在草地被乳草完全占领之前就能享用所有的牧草.她很好奇到底乳草要多久才能占领整个草地.如 果乳草在0\red{0}时刻处于格(Mx,My)\red{(M_x,M_y),}那么在哪个时刻它们可以完全占领入侵整片草地呢(对给定的数据总是会发生?

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

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

乳草会在4\red{4}星期后占领整片土地

输入格式

1\red{1}行:4\red{4}个由空格隔开的整数X\red{X,}K,Mx\red{K, M_x,}My.\red{M_y.}

2\red{2}到第Y+1\red{Y+1}行:每行由X\red{X}个字符描述草地.

输出格式

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

样例

输入样例

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

输出样例

4