题目描述 奶牛们的全国冬季滑雪运动会的场地是一个M*N的矩阵。矩阵中的每个小方格上的数代表的是每块地方的高度,范围是0到1000000000之间的整数。
矩阵中某些小方格被认为是中转点,主办方希望能够设置一个最小的D值,使得每只奶牛从任意一个中转点出发都可以到达其他任意的中转点。每次行走都是向相邻的小方格移动的,相邻的小方格指得是上下左右直接相接的小方格。如果相邻的小方格之间的高度差的绝对值小于等于D,则奶牛可以在两个相邻的小方格之间移动。
请计算这个最小的D值,使得奶牛能够从任意一个中转点出发通过移动到达其他任意中转点。 输入 第一行是两个正整数M和N。 第二行到到M+1行,每行N个整数,表示每个小方格的高度。 第M+2行到第2M+1行,每行N个整数,要么是0,要么是1,1表示该位置所对应的小方格是中转点,0表示该位置所对应的小方格不是中转点。
输出
输出最小的D值。
样例输入
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
样例输出
21
提示 数据范围:1<=M,N<=500,每个小方格的高度范围是0到1000000000之间的整数。 样例说明:样例中,如果D=21,则中转点之间是相互可达的,如果D<21,则右上角的中转点就不能到达其他的中转点了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int e[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,i,j,a[510][510],d[510][510],x,y,t,w,bao,mid,b[250010],c[250010],f[510][510];
bool pd(int xx){
int t=w=1,fx,fy,i,sx,sy,j;
memset(f,0,sizeof(f));
b[1]=x;c[1]=y;f[x][y]=1;
while(t<=w){
fx=b[t];fy=c[t];
for(i=0;i<4;i++){
sx=fx+e[i][0];sy=fy+e[i][1];
if(sx<1||sy<1||sx>n||sy>m)continue;
if(f[sx][sy])continue;
if(abs(a[sx][sy]-a[fx][fy])<=xx)
b[++w]=sx,c[w]=sy,f[sx][sy]=1;
}
t++;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(d[i][j]&&!f[i][j])
return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
cin>>a[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
cin>>d[i][j];
if(d[i][j]==1)x=i,y=j;
}
t=0;w=1e9;bao=1e9;
while(t<=w){
mid=(t+w)/2;
if(pd(mid))bao=mid,w=mid-1;
else t=mid+1;
}
cout<<bao;
return 0;
}
而我却输出28