汽车拉力比赛

题目描述

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

赛场凹凸不平，所以被描述为 $N*M$ 的网格来表示海拔高度 $(1 \leq M,N \leq 500)$，每个单元格的海拔范围在 $0$ 到 $10^9$ 之间。

其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数 $D$，这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于 $D$ 。也就是说这个难度系数 $D$ 指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

输入格式

第 $1$ 行两个整数 $M$ 和 $N$。第 $2$ 行到第 $M+1$ 行，每行 $N$ 个整数描述海拔高度。第 $2+M$ 行到第 $1+2M$

行，每行 $N$ 个整数，每个数非 $0$ 即 $1$，$1$ 表示该单元格是一个路标。

输出格式

一个整数，即赛道的难度系数 $D$。

样例 #1

样例输入 #1

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

21

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef pair<int , int> PII;

const int N = 510;
int cnt_falg = 0;
int n,m;
//表示初始时标记的坐标
int x1, y1;

//记录地图的海拔
int high[N][N];

//记录各个标记
int flag[N][N];
bool st[N][N];

PII q[N * N];

int dx[4] = {-1, 0, 1, 0}; // 上、右、下、左
int dy[4] = {0, 1, 0, -1};

//宽度优先搜索
bool check(int mid)
{
    //因为是从一个标记开始的
    //所以cnt的初始值标记为1
    //表示在宽度优先搜索中所经过的flag的数量
    int cnt = 1;
    q[0] = {x1,y1};
    st[x1][y1] = true;
    int hh = 0 , tt = 0;
    while(hh <= tt)
    {
        auto t = q[hh++];
        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if(a < 1 || b < 1 || a > n || b > m) continue;
            if(st[a][b]) continue;
            //mid不能满足相邻单元格最大的海拔高度差
            if(abs(high[t.first][t.second] - high[a][b]) > mid) continue;

            st[a][b] = true;
            q[++tt] = {a,b};

            if(flag[a][b] == 1)
            {
                cnt ++;
                if(cnt == cnt_falg) return true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>high[i][j];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>flag[i][j];

    //统计路标数量
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(flag[i][j] == 1) cnt_falg++;

    //无所谓x1和y1来到了哪个flag
    //只要从任意标记能到达其他的几个标记点即可
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(flag[i][j] == 1)
            {
                x1 = i, y1 = j;
            }

    //二分
    int l = -1 , r = 1e9 + 1;
    while(l + 1 != r)
    {
        int mid = (l + r) >> 1;
        //每一次二分都需要初始化
        memset(q,0,sizeof q);
        memset(st,false,sizeof st);
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout<<r<<endl;

    return 0;
}