4936：[USACO09OCT] Invasion of the Milkweed G

# [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