说明
“哞林匹克”运动会中的一大亮点就是滑雪比赛。滑雪比赛的场地是一个 \(n \times m\) 的矩阵（\(1<=n,m<=500\)），每一个点有对应的海拔(海拔均在 \(0\) 到 \(10^9\) 的范围内)。
主板方指定了若干个点作为路标。同时，主办方还要规定一个比赛系数 \(d\) ，这个系数规定选手不能在海拔高度差大于 \(d\) 的两个点之间活动。在规则允许的范围内，选手可以向东南西北任意一个点活动，选手的任务是在尽量短的时间内到达所有的路标打卡。
为了确保每一个选手的安全，主办方想将系数d设置得越小越好，然而这个系数要确保每一个路标是相互联通的（否则比赛就失去了意义）。
输入格式
第一行输入两个整数n和m，表示比赛场地的大小；
接下来输入两个 \(n \times m\) 的矩阵，第一个表示每一个点的海拔高度，第二个矩阵表示路标的设置情况，其中数字 \(1\) 表示该点为路标，数字 \(0\) 表示不是路标。
输出格式
输出 \(d\)。
样例
输入数据 \(1\)
3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
输出数据 \(1\)
21
-------------------------------------------------------
分析
本题每次枚举 \(d\)。每次 BFS 遍历一遍地图，如果发现一个点到另一个点距离大于 \(d\) 的话，则不走这条路。否则把这个新的点加入队列。
不过本题的 \(d\) 高达 \(10^9\)，所以暴力枚举肯定是不行的，因此，我们就要用上二分答案来解决这道题了。
代码
#include <bits/stdc++.h>
#define int long long //开个long long，以防万一
using namespace std;
int n, m, l = 0, r = 1e9, ans = INT_MAX, map1[510][510], map2[510][510]; //map1表示地图，map2表示打卡点
int dx[4] = {0, 1, 0, -1}; //方位数组
int dy[4] = {1, 0, -1, 0};
bool vis[510][510];
struct node {
int x, y; //记录一个坐标
};
bool check(int d) {
memset(vis, 0, sizeof(vis)); //更新数组
vis[1][1] = 1; //起点设为1
queue<node>q;
q.push({1, 1}); //把起点放进去
while(!q.empty()) {
int x = q.front().x; //取出队头元素
int y = q.front().y;
q.pop();
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i]; //新的一个坐标
if(tx < 1 || tx > n || ty < 1 || ty > m || vis[tx][ty] || abs(map1[x][y] - map1[tx][ty]) > d) continue; //判断是否可以到达新的点
q.push({tx, ty}); //放入队列
vis[tx][ty] = 1; //进行记录
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if(map2[i][j] && !vis[i][j]) //如果这个点是打卡点并且还没有走到
return 0; //则返回0
return 1; //否则返回1
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map1[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map2[i][j];
while(l <= r) {
int mid = (l + r) / 2;
if(check(mid)) ans = min(mid, ans), r = mid - 1; //如果可以，记录答案，并且看看能否找到更小的
else l = mid + 1; //否则找更大的
}
cout << ans << endl;
return 0;
}