Solution
需要找到最小满足题意的\(d\),显然\(d\)满足单调性,考虑二分
二分\(d\),然后直接bfs,每次bfs判断能不能走的时候还需要加上高度差不超过二分的\(d\)(即满足),bfs跑完后看看所有的路标都被访问了没。(可以记录个数,因为不可能重复走)
二分的时候注意\(l\)从0开始,不然会WA on test 5(答案可以为0)
还是一道很有意思的bfs呢
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PAIR;
int m,n;
int mapp[N][N];
int mark[N][N];
int sx,sy;
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int std_mark = 0;
bool check(int d)
{
queue <PAIR> q;
q.push(PAIR(sx,sy));
vis[sx][sy] = 0;
int cnt = 1;
while(!q.empty())
{
if(cnt == std_mark) return true;
PAIR p = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int ax = p.first + dx[i];
int ay = p.second + dy[i];
if(ax>=1&&ax<=m&&ay>=1&&ay<=n&&vis[ax][ay] == INF&&abs(mapp[p.first][p.second] - mapp[ax][ay])<=d)
{
if(mark[ax][ay])
{
// cout<<"ok"<<endl;
cnt ++;
}
q.push(PAIR(ax,ay));
vis[ax][ay] = 1;
}
}
}
if(cnt == std_mark) return true;
else return false;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) scanf("%d",&mapp[i][j]);
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&mark[i][j]);
if(mark[i][j]) sx=i,sy=j,std_mark ++;
}
}
int l = 0,r = INF;
while(l <= r)
{
// cout<<l<<" "<<r<<endl;
memset(vis,INF,sizeof(vis));
int mid = (l+r)/2;
if(check(mid)) r = mid -1;
else l = mid + 1;
}
cout<<l<<endl;
return 0;
}
标签:二分,拉力,int,mark,bfs,LuoguP2658,PAIR,include,刷题
From: https://www.cnblogs.com/SXqwq/p/17455232.html