洛谷2658 汽车拉力比赛 二分

题目链接:

https://www.luogu.org/problem/show?pid=2658

题意:

题解:

二分D，BFS判断是否可以到达全部路标。 很有道理啊，为什么T啊！

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ////////////////////////////////////////////////////////////////////////// const int maxn = 500+10; int n,m,sx,sy,sum; int G[maxn][maxn],is_p[maxn][maxn],vis[maxn][maxn]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; struct node{ int x,y; }; bool ok(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m && !vis[x][y]; } bool check(int x){ MS(vis); queue<node> q; q.push(node{sx,sy}); vis[sx][sy] = 1; int cnt = 1; while(!q.empty()){ node now = q.front(); q.pop(); for(int i=0; i<4; i++){ int tx=now.x+dx[i]; int ty=now.y+dy[i]; if(ok(tx,ty) && abs(G[tx][ty]-G[now.x][now.y]) <= x){ vis[tx][ty] = 1; q.push(node{tx,ty}); cnt += is_p[tx][ty]; if(cnt == sum) return true; } } } // return cnt == sum; return false; } int main(){ n=read(),m=read(); int mi=INF,mx=-1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){ G[i][j]=read(); mi=min(mi,G[i][j]); mx=max(mx,G[i][j]); } for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){ is_p[i][j]=read(); sum += is_p[i][j]; if(is_p[i][j]) sx=i,sy=j; } int L=0,R=mx-mi,ans=0; while(L<=R){ int mid = (L+R)/2; if(check(mid)) ans=mid,R=mid-1; else L=mid+1; } cout << ans << endl; return 0; }