P2658 汽车拉力比赛

题目描述

博艾市将要举行一场汽车拉力比赛。

赛场凹凸不平，所以被描述为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
2
3
4
5
6
7
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

1
21

bfs + 二分… 题目要求路标之间互达的最小落差，只要判断一个路标到其他路标是否可达即可，其它路标可以绕道过去，所以只需判断一次！如何判断到达所有路标呢？如上，路标标记为 1 ，其它为 0 ，所以 $cnt += g[ i][j]$ 并判断就行。（题解区大佬思路）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int MAX=500+10;
int n,m,a[MAX][MAX],g[MAX][MAX],ans=0,sum,fx,fy;
int vis[MAX][MAX];
int aw[4][2]={-1,0,0,1,1,0,0,-1};
struct node{
	int x,y;
	node(int _x,int _y){
		x=_x;y=_y;
	}
};
bool judge(int x,int y){
	if(x<1 || x>n ||y<1 ||y>m) return false;
	return true;
}
inline bool bfs(int d){
	int cnt =0;
	queue<node>q;
	q.push(node(fx,fy));
	vis[fx][fy]=d;
	while(!q.empty()){
		node t= q.front();
		q.pop();
		cnt += g[t.x][t.y];
		if(cnt == sum) return true;
		fi(i,0,4){
			int tx = t.x +aw[i][0],ty = t.y +aw[i][1];
			if(judge(tx,ty) && vis[tx][ty] != d && abs(a[t.x][t.y] - a[tx][ty]) <= d){
				vis[tx][ty] = d;
				q.push(node(tx,ty));
			}
		}
	}
	return false;
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	mem(vis,0);
	int _max=0;
	fi(i,1,n+1) fi(j,1,m+1){
		sf(a[i][j]);
		_max=max(_max,a[i][j]);
	}
	fi(i,1,n+1) fi(j,1,m+1){
		sf(g[i][j]);
		if(g[i][j]) {
			sum ++;
			if(sum==1) {
				fx = i;fy =j;
			}
		}
	}
	int l = 0,r=_max;
	while(l<=r){
		int m =(l+r)/2;
		if(bfs(m)){
			ans = m;
			r= m-1;
		}else l=m+1;
	} 
	pf(ans);
	return 0;
}