BOJ 2169 — Robot Control

Problem: BOJ 2169 — Robot Control · 한국어 · 日本語

A robot starts at the top-left cell of an N × M grid and must reach the bottom-right cell. Each cell contributes its value to the score. The robot may move left, right, or down, but never up, and it may not visit a cell more than once. The goal is to maximize the sum of the visited values.

The key is to process the grid one row at a time. A path can enter a row only from above, and after traveling within that row it must leave downward. Since upward movement is forbidden, its horizontal moves in that row can only go in one direction: moving in both directions would revisit a cell. Thus, for each cell, the best path reaching it in the current row either came from the cell above or continued horizontally from a neighboring cell in that same row.

For a row, let above[c] be the best score reaching column c in the previous row. A left-to-right sweep computes the best score that arrives from above or continues from the left. A right-to-left sweep computes the corresponding best score from above or from the right. The pointwise maximum of these two sweeps is the best score for each cell in the row. The first row is seeded only at its leftmost cell; this handles the start without allowing a path to begin elsewhere.

Unreachable states use a negative-infinity sentinel, so negative cell values are handled correctly rather than being mistaken for an unvisited/default score. The DP retains only the previous row and two sweep arrays, taking O(NM) time and O(M) auxiliary memory.

C++17

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<vector<long long>> value(n, vector<long long>(m));
    for (auto& row : value) {
        for (long long& cell : row) cin >> cell;
    }

    constexpr long long NEG = numeric_limits<long long>::lowest() / 4;
    vector<long long> above(m, NEG), leftToRight(m), rightToLeft(m);

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            const long long fromAbove = above[c];
            const long long fromLeft = (c > 0) ? leftToRight[c - 1] : NEG;
            if (r == 0 && c == 0) {
                leftToRight[c] = value[r][c];
            } else {
                leftToRight[c] = max(fromAbove, fromLeft) + value[r][c];
            }
        }

        for (int c = m - 1; c >= 0; --c) {
            const long long fromAbove = above[c];
            const long long fromRight = (c + 1 < m) ? rightToLeft[c + 1] : NEG;
            if (r == 0 && c == 0) {
                rightToLeft[c] = value[r][c];
            } else {
                rightToLeft[c] = max(fromAbove, fromRight) + value[r][c];
            }
        }

        for (int c = 0; c < m; ++c) {
            above[c] = max(leftToRight[c], rightToLeft[c]);
        }
    }

    cout << above[m - 1] << '\n';
    return 0;
}