汽车拉力比赛
题目描述
博艾市将要举行一场汽车拉力比赛。
赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之间。
其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D,这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。
输入格式
第一行两个整数M和N。第2行到第M+1行,每行N个整数描述海拔高度。第2+M行到第1+2M
行,每行N个整数,每个数非0即1,1表示该单元格是一个路标。
输出格式
一个整数,即赛道的难度系数D。
样例 #1
样例输入 #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
//带点二分的味道,但实际还是bfs的方法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;
int n, m;
int high[N][N]; //存海拔高度
int flag[N][N]; //路标
int cnt_flag = 0;
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &high[i][j]);
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", flag[i][j]);
}
}
//int cnt_flag = 0; //统计路标总数 //放到全局变量中,使得bfs可以少传一个参数
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &flag[i][j]);
if(flag[i][j] == 1){
cnt_flag++;
}
}
}
int x1, y1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(flag[i][j] == 1){
x1 = i, y1 = j;
break; //找到一个“1”路标就行,就可以开始bfs
}
}
}
//二分思路
int l = -1,r = 1e9 + 10;
while(l + 1 < r){
}
}