BOJ 1520 - Downhill Paths

BOJ 1520 - Downhill

Idea: dynamic programming on a DAG

Treat each cell as a vertex. There is a directed edge from a cell to each of its four orthogonally adjacent cells whose height is strictly lower. Every edge decreases height, so a directed cycle is impossible: this graph is a DAG. Equal-height neighbors have no edge between them.

We need the number of directed paths from the top-left cell to the bottom-right cell. A recursive depth-first search with memoization expresses the recurrence directly, but a path can contain as many as $M N = 250{,}000$ cells. Recursing along such a path risks exhausting the call stack. Instead, process the cells in ascending order of height, which is a topological order for this graph with its edges reversed.

Let dp[r][c] be the number of downhill paths from (r,c) to the destination. Initialize the destination to one: the empty continuation from the destination to itself is one path. When processing a cell u, all lower neighbors have already been processed. For each in-bounds higher neighbor v, add dp[u] to dp[v]. This is the reversed-edge recurrence: every path from v to the destination must first step to one of its lower neighbors, and u contributes exactly the paths that start with v -> u. When a cell is reached in the ascending order, all its lower-neighbor contributions are final. The answer is dp[0][0].

Check the four directions separately and ignore any coordinate outside the grid. The strict height comparison excludes equal-height moves; such cells cannot be connected by a downhill step.

Exact arithmetic and complexity

The official limits are $1 \le M,N \le 500$ and heights from 1 through 10,000. A path count is not bounded by the number of cells: many distinct routes can merge at a cell, so a fixed-width integer is not guaranteed to hold the answer. The implementation uses boost::multiprecision::cpp_int for exact counts.

Let $V=MN$, $E$ be the number of adjacent pairs with unequal heights (each contributes one directed edge), and $B$ the maximum bit length of any path count. Sorting takes $O(V\log V)$ comparisons; the grid has at most $4V$ directed edges. With arbitrary-precision integers, the additions take $O(E B)$ bit operations in the usual linear-cost model for addition, so total time is $O(V\log V + E B)$. Storage is $O(V)$ grid/order entries plus the stored integers; in bit space, the DP values can occupy up to $O(VB)$ bits in the worst case.

C++17

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

struct Cell {
    int height;
    int row;
    int col;
};

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

    int rows, cols;
    cin >> rows >> cols;

    vector<vector<int>> height(rows, vector<int>(cols));
    vector<Cell> order;
    order.reserve(static_cast<size_t>(rows) * cols);
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            cin >> height[r][c];
            order.push_back({height[r][c], r, c});
        }
    }

    sort(order.begin(), order.end(), [](const Cell& a, const Cell& b) {
        return a.height < b.height;
    });

    vector<vector<cpp_int>> dp(rows, vector<cpp_int>(cols));
    dp[rows - 1][cols - 1] = 1;

    constexpr array<int, 4> dr = {-1, 1, 0, 0};
    constexpr array<int, 4> dc = {0, 0, -1, 1};

    for (const Cell& cell : order) {
        const int r = cell.row;
        const int c = cell.col;
        for (int direction = 0; direction < 4; ++direction) {
            const int nr = r + dr[direction];
            const int nc = c + dc[direction];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (height[nr][nc] > height[r][c]) {
                dp[nr][nc] += dp[r][c];
            }
        }
    }

    cout << dp[0][0] << '\n';
    return 0;
}