BOJ. Slope (14890)

Problem: BOJ 14890 — Slope · 한국어 · 日本語

A runway can be built on a row or column when every height change between neighboring cells is exactly 0 or 1, and each height difference of 1 can be covered by a length-L ramp. A ramp occupies L cells on the lower side of the height change. Those cells must all have the same height, stay within the line, and not have been used by another ramp.

Validate one line from left to right while tracking which cells already hold a ramp. Equal neighboring heights need no action. For an upward step, the lower side is the L cells immediately before the step; for a downward step, it is the L cells beginning at the next cell. Check bounds, equal heights across that segment, and overlap before marking the cells as used. This explicit occupancy check prevents consecutive descents from reusing the same cells. A height difference greater than 1, an unavailable segment, or any overlap makes the line invalid. Run this validator on every row and every column.

Each segment can hold a ramp only once. The two sides of a ramp transition must have equal height, while adjacent height differences greater than 1 are always invalid. With N <= 100, checking up to L cells for each of N transitions in each of 2N lines takes O(N^2 * L) time. The height grid uses O(N^2) space, and the line plus ramp-occupancy scratch uses O(N) space.

C++17

#include <iostream>
#include <vector>

using namespace std;

bool canBuildRunway(const vector<int>& line, int length) {
    const int n = static_cast<int>(line.size());
    vector<bool> used(n, false);

    for (int i = 0; i + 1 < n; ++i) {
        const int difference = line[i + 1] - line[i];
        if (difference == 0) continue;
        if (difference < -1 || difference > 1) return false;

        const int start = difference == 1 ? i - length + 1 : i + 1;
        const int end = difference == 1 ? i : i + length;
        if (start < 0 || end >= n) return false;

        const int lowerHeight = difference == 1 ? line[i] : line[i + 1];
        for (int cell = start; cell <= end; ++cell) {
            if (line[cell] != lowerHeight || used[cell]) return false;
        }
        for (int cell = start; cell <= end; ++cell) {
            used[cell] = true;
        }
    }

    return true;
}

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

    int n, length;
    cin >> n >> length;

    vector<vector<int>> height(n, vector<int>(n));
    for (auto& row : height) {
        for (int& cell : row) cin >> cell;
    }

    int answer = 0;
    vector<int> line(n);

    for (int row = 0; row < n; ++row) {
        if (canBuildRunway(height[row], length)) ++answer;
    }

    for (int column = 0; column < n; ++column) {
        for (int row = 0; row < n; ++row) {
            line[row] = height[row][column];
        }
        if (canBuildRunway(line, length)) ++answer;
    }

    cout << answer << '\n';
    return 0;
}