[USACO09OCT] 马利筋入侵 G

题目描述

农夫约翰一直尽力让牧场长满肥美、美味又健康的青草供奶牛食用。然而他还是输掉了这场战斗，因为邪恶的马利筋在他农场的西北角扎下了根。

牧场照常被划分成一个直角网格，高度为 (Y)（(1\le Y\le 100)），宽度为 (X)（(1\le X\le 100)），坐标 ((1,1)) 位于左下角（即按照常规的 (X,Y) 坐标系排布）。马利筋最初从方格 ((Mx,My)) 开始生长。 每周，马利筋都会向所有已占据方格周围非岩石的方格蔓延，最多可扩展到 8 个相邻方格（包括上下左右及四个对角线方向）。这些方格被侵占一周后，马利筋就可以继续向更多方格蔓延。

贝茜想在牧场被马利筋完全占领前尽可能多地享用青草。她想知道牧场还能坚持多久。已知马利筋在时间 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 周后占领了整片区域。

输入格式

• 第 1 行：四个用空格分隔的整数 (X,Y,Mx,My)
• 第 2 至 (Y+1) 行：第 (y+1) 行描述牧场的第 ((Y+2-y)) 行，每行包含 (X) 个字符（. 为草地，* 为巨石）

输出格式

• 第 1 行：一个整数，表示马利筋占领最后一块非巨石方格时的周数。

输入样例1：

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

输出样例1：

4 

提示

（暂无提示）

标签：P2960|搜索|2009|USACO

来源

P2960|[USACO09OCT] Invasion of the Milkweed G