123456
2024-10-19 15:59:01
发布于：浙江
https://www.acgo.cn/contest/detail/4651?matchRoundId=4651&examId=47410&teamCode=1691092370071752704&openLevel=2
全部评论 1
#include<bits/stdc++.h>
using namespace std;
int m,n;
long long h[510][510];
bool vis[510][510];
int a[510][510];
int sx,sy,num=0;
struct node{
int x,y;
};
int dx[4]={1,0,-1,0},
dy[4]={0,1,0,-1};
bool check(int d,int nu){
queue<node> q;
q.push({sx,sy});
vis[sx][sy]=1;
nu--;
while(!q.empty()){
int x=q.front().x;
int y=q.front().y;
q.pop();
for(int i=0;i<4;i++){
int x1=dx[i]+x;
int y1=dy[i]+y;
if(x1>=1&&x1<=m&&y1>=1&&y1<=n&&vis[x1][y1]==0&&abs(h[x][y]-h[x1][y1]<=d)){
q.push({x1,y1});
vis[x1][y1]=1;
if(a[x1][y1]==1) nu--;
}} } if(nu==0) return 1; return 0;}
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>h[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==1){
sx=i;
sy=j;
num++;
}
}
}
long long l=0,r=1e9;
long long ans=-1;
while(l<=r){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
vis[i][j]=0;
}
}
long long mid=(l+r)/2;
if(check(mid,num)){
ans=mid;
l=mid-1;
}
else{
r=mid+1;
}
}
cout<<ans;
return 0;
}3天前 来自 浙江
0
有帮助，赞一个