J8 实践-6 鲜花满园

题目描述

猪猪学校的小花园里，矩形的草坪上，有一粒蒲公英种子落下来了，并且要实现鲜花满园的扩张。 草坪是一个 $n \times m$ 格的矩形，蒲公英的种子在 $0$ 天落在了左下角，坐标为 $(1,1)$ 的格子上。 每一天，蒲公英都会把种子扩散到相邻的格子（四面八方地撒，除非格子上是石头）。请问，蒲公英的种子要多少天才能撒满整个花园？ 1） $"."$ 表示草地； 2） $"*"$ 表示石头； 草地的初始状态如下：

....
..*.
.**.

第 $0->4$ 天，蒲公英的生长情况，如下图所示：

DAY0 -> DAY1 -> DAY2 -> DAY3 -> DAY4
....    ....    FFF.    FFFF    FFFF
..*.    FF*.    FF*.    FF*F    FF*F
F**.    F**.    F**.    F**.    F**F

输入格式

共 $n+1$ 行， 第一行是四个整数 $n,m$ 和 $x,y$ ，表示草地是 $n$ 行 $m$ 列的，蒲公英在第 $0$ 天落在的坐标是 $(x,y)$ 。 接下来的 $n$ 行中，每行包括 $m$ 个字符（字符之间没有空格）。

输出格式

一个整数，表示鲜花满园需要花费的天数。

样例输入

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

样例输出

4

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有 $1 \leq n,m \leq 100$ 。