(四连测)滑雪场的高度差题解---二分 + 搜索---DD(XYX)的博客

滑雪场的高度差

时间限制: 1 Sec 内存限制: 128 MB

题目描述

滑雪场可以看成M x N的网格状山地(1 <= M,N <= 500),每个网格是一个近似的平面，具有水平高度值在0 .. 1,000,000,000米的范围内。

某些网格被指定为关键网格。当两个相邻网格之间的高度差的绝对值不超过某个参数D时，就可以相互到达。相邻关系是指某个格子的东、西、南、北的格子。

显然，当D不断减小时，原本可以相互到达的相邻格子就不能到达了。

滑雪赛的组委会想知道，为了保证各个关键网格之间彼此连通，最小的D是多少？

输入

第1行：2个整数M和N

接下来M行，每行N个整数，表示各网格的高度

接下来M行，每行N个0或者1，1表示关键网格

输出

第1行：1个整数，表示最小的D

方法

因为这题和二分求解有一个共同点。即若 D = x 时，关键网格之间彼此连通，则 D = (x + 1) 时，关键网格之间肯定更彼此连通，所以就跟 “ 在单调序列中寻找值 ” 有相同点了。故此题要用二分 + 搜索求解。

（XYF：）至于搜索，优选bfs（节省时间）。在合法情况下搜索一次（起点下文解释），存哪些网格经历过，最后再判断是否经过了所有关键网格。起点最先想到的肯定是从每一个关键网格出发，看看从它开始搜索，在合法情况下是否能经过所有关键网格（输入时可以用结构体，存下每一个关键网格的坐标，关键网格的数量）。但试想，从任意一个关键网格出发，如果它能经过所有关键网格，这个mid就是可以采用的呢？因为假如从某一关键网格（x,y）出发，它通过某一路径经过一个关键网格（m,n），那么从（m,n）出发也一定能通过这个路径，以现在的 mid 经过（x,y）。所以假如（x,y）能经过所有的关键网格，那么（m,n）也一定能经过所有的关键网格（它先沿某一路径到达（x,y））。所以只用从任意一个关键网格开始搜索，再判断。如果它经过了所有关键网格，bfs() 返回true，不然返回false。

其中有一些小坑，曾经把我害的惨，

1，要用 bfs 的话，vis[][] 的计算，清空，判断很重要。

2，二分防爆。

-> 3，若要用 “ while(l < r) ” 的人注意，退出循环后，mid 还没更新成 (l + r) / 2，除非在循环节末尾更新 mid ，不然不能直接输出 mid 。

4，判断绝对值 abs() 函数最好不要用宏定义，不然要错，除非使用时这样写：abs( ( ...... ) ) 。

以下代码：(考察良心的时候到了)

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

#define abs(x) (x < 0 ? -x : x)

using namespace std;

void read(int &x) {

    int f = 1;x = 0;char s = getchar();

    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}

    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

    x *= f;

}

struct no{

    int x,y;

    no(){}

    no(int X,int Y){

        x = X;y = Y;

    }

};

int n,m,s,o,i,j,k,ans = 0,nm,fx,fy,ji = 0;

int a[505][505],d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

bool f[505][505],v[505][505];

bool bfs(int xx) {

    memset(f,0,sizeof(f));

    ji = 0;

    queue<no> b;

    b.push(no(fx,fy));

    f[fx][fy] = 1;

    while(!b.empty()) {

        no t = b.front();

        b.pop();

        if(v[t.x][t.y]) {

            ji ++;

        }

        if(ji == nm) {

            return 1;

        }

        for(int i = 0;i < 4;i ++) {

            no t1 = t;

            t1.x += d[i][0];

            t1.y += d[i][1];

            if(!f[t1.x][t1.y] && t1.x > 0 && t1.x <= n && t1.y > 0 && t1.y <= m && abs((a[t1.x][t1.y] - a[t.x][t.y])) <= xx) {

                f[t1.x][t1.y] = 1;

                b.push(t1);

            }

        }

    }

    return 0;

}

int js(int l,int r) {

    int mid = (l + r) / 2;

    while(l < r) {

        bool ff = bfs(mid);

        if(ff) r = mid;

        else l = mid + 1;

        mid = (l + r) / 2;

    }

    return mid;

}

int main() {

    read(n);read(m);

    for(i = 1;i <= n;i ++) {

        for(j = 1;j <= m;j ++) {

            read(a[i][j]);

            o = max(o,a[i][j]);

        }

    }

    for(i = 1;i <= n;i ++) {

        for(j = 1;j <= m;j ++) {

            read(k);

            if(k == 1) v[i][j] = 1,fx = i,fy = j,nm ++;

        }

    }

    printf("%d",js(0,o));

    return 0;

}

巴特西

(四连测)滑雪场的高度差题解---二分 + 搜索---DD(XYX)的博客

滑雪场的高度差

题目描述

输入

输出

方法

最新文章

热门文章

巴特西

(四连测)滑雪场的高度差题解---二分 + 搜索---DD(XYX)​​​​​​​的博客

滑雪场的高度差

题目描述

输入

输出

方法

最新文章

热门文章

(四连测)滑雪场的高度差题解---二分 + 搜索---DD(XYX)的博客