【题目来源】
洛谷：[P2960 USACO09OCT] Invasion of the Milkweed G - 洛谷
【题目描述】
农夫约翰一直尽力保持牧场里长满丰盛、美味且健康的草供奶牛食用。然而，他输掉了这场战斗，因为邪恶的乳草在他的农场西北部站稳了脚跟。
牧场通常被划分为一个直角网格，高度为 \(Y\)（\(1 \le Y \le 100\)），宽度为 \(X\)（\(1 \le X \le 100\)），其中 \((1,1)\) 位于左下角（即，排列为正常的 \(X,Y\) 坐标网格）。乳草最初开始在方格 \((M_x,M_y)\) 生长。每周，乳草会传播到它已经占据的任何方格周围的所有非岩石方格，最多可以传播到八个方格（包括直角方格和对角线方格）。在这些方格中仅仅一周后，它就准备好继续传播到更多方格。
贝茜想在牧场被乳草占领之前尽可能多地享受青草。她想知道牧场能持续多久。如果乳草在时间零时位于方格 \((M_x,M_y)\)，那么它在何时完成对牧场的入侵（对于给定的输入数据，这种情况总会发生）？
牧场由一个图示描述，'.' 代表草，'*' 代表巨石，如下例所示，\(X=4\)，\(Y=3\)：
....
..*.
.**.
如果乳草从左下角开始（行=1，列=1），那么地图将按如下方式演变：
.... .... MMM. MMMM MMMM..*. MM*. MM*. MM*M MM*MM**. M**. M**. M**. M**M
week 0 1 2 3 4
乳草在 4 周后占领了整个牧场。
【输入】
* 第 1 行：四个以空格分隔的整数：\(X\)，\(Y\)，\(M_x\) 和 \(M_y\)
* 第 2 行到第 \(Y+1\) 行：第 \(y + 1\) 行描述了牧场的第 \((Y + 1 - y)\) 行，其中包含 \(X\) 个字符（'.' 代表草，'*' 代表巨石）
【输出】
* 第 1 行：一个整数，表示乳草占领牧场最后一个非巨石方格的周数。
【输入样例】
4 3 1 1
....
..*.
.**.
【输出样例】
4
【算法标签】
《洛谷 P2960 Invasion of the Milkweed》 #搜索# #USACO# #2009#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 105; // 网格最大尺寸
int n, m, x, y, ans; // n: 行数，m: 列数，x,y: 起始坐标，ans: 最大步数
char a[N][N]; // 网格地图
bool vis[N][N]; // 访问标记数组
int dx[8] = {-1,-1,-1,0,0,1,1,1}; // 8个方向的行偏移量
int dy[8] = {-1,0,1,-1,1,-1,0,1}; // 8个方向的列偏移量struct Node
{int x, y, step; // 节点坐标和步数
};void bfs()
{queue<Node> q;q.push({x, y, 0}); // 起点入队vis[x][y] = 1; // 标记起点已访问while (!q.empty()){int xx = q.front().x, yy = q.front().y, step = q.front().step;q.pop();// 遍历8个方向for (int i = 0; i < 8; i++){int nx = xx + dx[i], ny = yy + dy[i]; // 计算新坐标// 检查边界if (nx < 1 || nx > n || ny < 1 || ny > m) continue;// 检查是否已访问if (vis[nx][ny]) continue;// 检查是否为障碍if (a[nx][ny] == '*') continue;// 标记访问并加入队列vis[nx][ny] = 1;q.push({nx, ny, step + 1});ans = max(ans, step + 1); // 更新最大步数}}
}int main()
{// 读入网格尺寸和起始坐标// 注意输入顺序：先列数m，再行数n，再列坐标y，再行坐标xcin >> m >> n >> y >> x;// 调整行坐标（题目坐标系与数组索引的转换）x = n - x + 1; // 将输入的行坐标转换为数组索引// 读入网格地图for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}// 标记起点为已访问状态a[x][y] = '#';// 开始广度优先搜索bfs();// 输出从起点出发能到达的最远步数cout << ans << endl;return 0;
}
【运行结果】
4 3 1 1
....
..*.
.**.
4