Editing 2014 Jan Silver Problem 2 Cross Country Skiing (section)

=== C++ (BFS) ===

<div class="mw-collapsible mw-collapsed">
    <h3 class="mw-collapsible-toggle" >Show Code</h3><br><br><br>
    <div class="mw-collapsible-content">

<pre>
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> elevation;
vector<vector<int>> destination;
int totalPoints, current;
int startX = -1, startY = -1;
int numRows, numCols;
int maxHeight = 0, minHeight = 1e9;

void bfs(int x, int y, int maxDiff) {
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(numRows, vector<bool>(numCols, false));
    q.push({x, y});
    visited[x][y] = true;

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

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

        current += destination[x][y];

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
                !visited[newX][newY] && abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
                q.push({newX, newY});
                visited[newX][newY] = true;
            }
        }
    }
}

bool isReachable(int maxDiff) {
    current = 0;
    bfs(startX, startY, maxDiff);
    return current >= totalPoints;
}

int main() {
    freopen("ccski.in", "r", stdin);
    freopen("ccski.out", "w", stdout);

    cin >> numRows >> numCols;
    totalPoints = 0;

    elevation.resize(numRows, vector<int>(numCols, 0));
    destination.resize(numRows, vector<int>(numCols, 0));

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> elevation[i][j];
            maxHeight = max(maxHeight, elevation[i][j]);
            minHeight = min(minHeight, elevation[i][j]);
        }
    }

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> destination[i][j];
            totalPoints += destination[i][j];
            if (startX < 0 && destination[i][j] == 1) {
                startX = i;
                startY = j;
            }
        }
    }

    int high = maxHeight - minHeight + 1;
    int low = 0;

    while (low < high) {
        int mid = (low + high) / 2;
        if (isReachable(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << high << endl;
}

</pre>
    </div>
</div>