11373: 【原1373】收集红旗比赛

题目描述

author: wkn/ssy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1373

Description

“年轻人啊，都是靡靡之音呐，都是轻歌曼舞呐，将来都是没有出息的。这个啊，就是要豪迈，比如要比赛爬山啊，比赛拔河啊。”

于是wkn毅然投入到了爬山比赛中（其实是为了素拓）。

这座山可以看做一个M x N的矩阵，矩阵里的每一项代表当前位置山的高度。

在山上插着好几面红旗，参赛选手可以选择任何一面红旗所在的点出发，目标是经过所有插红旗的地方。 wkn当然想获胜，于是就要找出一种方案，使得在爬山的过程中，任意相邻位置的海拔差的最大值最小。但是他最近被毕业论文逼得焦头烂额没时间写代码计算了，情你帮帮他。

Input Format

第一行为两个整数M，N(M，N不超过500)

接下里M*N表示每个位置山的高度

接下里M*N表示每个位置上是否有红旗

Output Format

一行一个整数，表示最打海拔差的最小值

Input Sample

Output Sample

FineArtz's solution

/* 收集红旗比赛 */
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

const int INF = 2147483647;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

class Point{
public:
    Point() = default;
    Point(int xx, int yy) : x(xx), y(yy) {}

    bool operator ==(Point p){
        return (x == p.x && y == p.y);
    }
    int x = 0, y = 0, minh = INF;
};

int h[505][505];
bool v[505][505];
vector<Point> fl;
int m, n;
int ans = 0, cnt = 0;

bool check(Point p){
    if (p.x < 1 || p.x > m || p.y < 1 || p.y > n || v[p.x][p.y]) return false;
    return true;
}

bool bfs(Point s, int lim){
    memset(v, 0, sizeof(v));
    queue<Point> q;
    q.push(s);
    v[s.x][s.y] = true;
    while (!q.empty()){
        Point now = q.front();
        q.pop();
        for (int i = 0; i != 4; ++i){
            Point next(now.x + dx[i], now.y + dy[i]);
            if (check(next)){
                int dh = abs(h[now.x][now.y] - h[next.x][next.y]);
                if (dh > lim) continue;
                q.push(next);
                v[next.x][next.y] = true;
            }
        }
    }
    for (auto f : fl){
        if (!v[f.x][f.y]) return false;
    }
    return true;
}

int main(){
    memset(h, 0, sizeof(h));
    cin >> m >> n;
    int minn = INF, maxx = 0;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j){
            cin >> h[i][j];
            minn = min(minn, h[i][j]);
            maxx = max(maxx, h[i][j]);
        }
    int flag;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j){
            cin >> flag;
            if (flag == 1){
                fl.emplace_back(i, j);
            }
        }
    Point s = *(fl.begin());
    fl.erase(fl.begin());
    s.minh = 0;
    int low = 0, high = maxx - minn, mid = (low + high) / 2;
    while (low < high){
        mid = (low + high) / 2;
        if (bfs(s, mid))
            high = mid;
        else
            low = mid + 1;
    }
    cout << low << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define MAX_N 505
using namespace std;
struct data {
    int height;
    bool flag;
} a[MAX_N][MAX_N];
struct Node {
    int x, y;
    Node(int p = 0, int q = 0): x(p), y(q) {}
}s;
const int step[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
int n, m, cnt, l, r, rest;
bool vis[MAX_N][MAX_N];
queue<Node> q;
inline int read() {
    char ch = getchar(); int res = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res;
}
inline void clear(queue<Node> &q) {
    queue<Node> empty;
    swap(empty, q);
}
bool check(const int& delta_height) {
    while (!q.empty() && rest) {
        Node cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            Node next(cur.x + step[i][0], cur.y + step[i][1]);
            if (next.x >= 0 && next.x < n && next.y >= 0 && next.y < m &&
            !vis[next.x][next.y] && abs(a[next.x][next.y].height - a[cur.x][cur.y].height) <= delta_height) {
                vis[next.x][next.y] = true;
                if (a[next.x][next.y].flag) --rest;
                q.push(next);
            }
        }
    }
    if (rest) return false;
    else return true;
}
int main() {
    n = read(), m = read();
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j) {
            a[i][j].height = read();
            r = max(r, a[i][j].height);
        }
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j) a[i][j].flag = read();
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j)
            if (a[i][j].flag) {
                s.x = i, s.y = j;
                ++cnt;
            }
    l = 0;
    while (l < r) {
        int mid = (l + r) >> 1;
        clear(q); q.push(s);
        memset(vis, false, sizeof(vis)); vis[s.x][s.y] = true;
        rest = cnt - 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d", l);
    return 0;
}