题目传送门：
P7775 [COCI 2009/2010 #2] VUK - 洛谷 (luogu.com.cn)
前言：
这道题的核心目标是找出狼从起点 V 到终点 J 的路径，使得狼在途中离它最近的树的距离的最小值最大。下面为大家详细讲解：
#整体思路概述：
这道题我们可以采用“先计算距离，再来二分查找”的策略。具体来说，先算出森林中每个格子到最近树的距离，接着利用二分查找来确定满足条件的最大的最小距离。
##具体步骤：
1、数据输入与存储：
读取森林的行数 n 和列数 m 。
读取森林的布局，使用二维字符数组 forest 来存储记录狼的起始位置 （sx,sy） 和窝的位置 (tx,ty).
2、计算每个格子到最近树的距离：
我们采用广度搜索BFS算法。（这里就不讲BFS的用法了，如果想了解或者不知道的话可以点这个链接新手学习BFS与DFS ? 用时4小时整理了BFS (广度优先搜索） DFS（深度优先搜索）字数已超4000字_先学bfs和dfs哪个档次高-CSDN博客）
初始化一个距离数组 ist ，将所有元素的初始化为无穷大 N 。
把所有树的位置假如队列，这里为止到自身的距离为 0 。
从队列中取出一个位置 （x,y），检查四个相邻位置(nx,ny)。如果相邻位置违背访问过的话，则更新该位置的距离为当前位置的距离 + 1 ，并将其加入队列。
重复上述的步骤，直到队列为空。这样我们就可以得到每个格子到最近树的曼哈顿距离。
3、二分查找最大的最小距离：
设定二分查找左右边界，左边 定义 left 初始化为 0 ，右边 定义 right 初始化微 n + m。
取中间值 mid ,调用 canreach 函数判断是否能以 mid 为最大最小距离。
4、判断是否能以指定最小距离到达终点：
同样适用 广度搜索 算法。
初始化一个访问标记数组为 vis ，将所有元素初始化为 cntfa。
从起点开始，如果起点到最近树的距离小于 min ，则直接返回 false 。
将起点假如队列，并标记为已访问。
从队列中取出一个位置 (x,y) ，检查其四个相邻位置 (nx,ny) 。 如果相邻位置未被访问过且到最近树的距离大于等于 min 则将其 加入队列并标记为已访问。
重复上面此步骤，知道队列为空或到达终点。如果到达终点，则返回 true ；否则范围 false。
###复杂度分析：
1、时间复杂度：
时间复杂度为 。
2、空间复杂度：
空间复杂度为 。
####代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int N = 0x3f3f3f3f;
int n, m;
char forest[MAXN][MAXN];
int ist[MAXN][MAXN];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int sx, sy, tx, ty;// 计算每个格子到最近树的距离
void tree() {queue<pair<int, int>> q;memset(ist, N, sizeof(ist));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (forest[i][j] == '+') {q.push({i, j});ist[i][j] = 0;}}}while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int i = 0; i < 4; ++i) {int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m && ist[nx][ny] == N) {ist[nx][ny] = ist[x][y] + 1;q.push({nx, ny});}}}
}// 判断是否能以 min 为最小距离从起点到终点
bool reach(int min) {queue<pair<int, int>> q;bool vis[MAXN][MAXN];memset(vis, false, sizeof(vis));if (ist[sx][sy] < min) return false;q.push({sx, sy});vis[sx][sy] = true;while (!q.empty()) {auto [x, y] = q.front();q.pop();if (x == tx && y == ty) return true;for (int i = 0; i < 4; ++i) {int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m &&!vis[nx][ny] && ist[nx][ny] >= min) {q.push({nx, ny});vis[nx][ny] = true;}}}return false;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> forest[i][j];if (forest[i][j] == 'V') {sx = i;sy = j;} else if (forest[i][j] == 'J') {tx = i;ty = j;}}}tree();int left = 0, right = n + m;int ans = 0;while (left <= right) {int mid = (left + right) / 2;if (reach(mid)) {ans = mid;left = mid + 1;} else {right = mid - 1;}}cout << ans << endl;return 0;
}
