题解

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

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

int M, N;
vector<vector<long long>> height; // 海拔矩阵
vector<vector<int>> is_sign;      // 是否是路标（1表示是）
vector<pair<int, int>> signs;     // 所有路标的坐标

// 验证当前D是否能让所有路标连通
bool check(int D) {
    vector<vector<bool>> visited(M, vector<bool>(N, false));
    queue<pair<int, int>> q;

    // 从第一个路标开始BFS
    int start_x = signs[0].first;
    int start_y = signs[0].second;
    q.push({start_x, start_y});
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 边界检查 + 未访问 + 海拔差≤D
            if (nx >= 0 && nx < M && ny >=0 && ny < N && !visited[nx][ny] && abs(height[x][y] - height[nx][ny]) <= D) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    // 检查所有路标是否都被访问到
    for (auto [x, y] : signs) {
        if (!visited[x][y]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> M >> N;
    height.resize(M, vector<long long>(N));
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> height[i][j];
        }
    }

    is_sign.resize(M, vector<int>(N));
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> is_sign[i][j];
            if (is_sign[i][j] == 1) {
                signs.emplace_back(i, j);
            }
        }
    }

    // 二分查找最小D
    int left = 0, right = 1e9;
    int ans = 1e9;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << endl;
    return 0;
}