Summary

This problem asks us to choose exactly one tile from each row of an R x C grid. Consecutive choices must touch by an edge or a corner, so from column j in one row, the next row can use column j - 1, j, or j + 1.

Each tile has a cost generated by a repeating row-major sequence:

1, 2, 3, ..., M, 1, 2, 3, ..., M, ...

The goal is to find the minimum possible total cost from the first row to the last row.

The key idea is dynamic programming. We keep the best cost to reach each column in the current row. Since each row only depends on the previous row, we can use rolling arrays and reduce memory to O(C).

本题在 CCC 数据结构与算法路线图中的位置

• Level: Junior J5
• Pattern: Grid Dynamic Programming, Local Transitions, Rolling Array Optimization
• Prerequisite: 2D grids, arrays/lists, loops, minimum updates, row-major indexing
• What this teaches: Define a DP state for each position, transition from nearby previous states, and reduce memory when only the previous row is needed.
• Where it appears again: grid DP, path counting, obstacle DP, DAG DP, interval DP

What to Study Next

• Related CP Weekly problems: CCC 2015 J5 Pi Day for beginner DP and memoization (coming soon), CCC 2012 S5 Mouse Journey for grid DP with obstacles (coming soon), CCC 2007 S4 Waterpark for DAG DP (coming soon).
• Related Python / C++ foundations: lists/vectors, 2D arrays, nested loops, functions, integer minimum updates.
• Related DSA roadmap article: CCC Dynamic Programming Roadmap: state, transition, order (planned).

理解题目

We have an R x C grid. We must start in row 0 and end in row R - 1, choosing exactly one tile in every row.

If we choose column j in the previous row, then in the next row we may choose:

• j - 1
• j
• j + 1

as long as that column exists.

The tile costs are not given directly. They are generated in row-major order:

1, 2, 3, ..., M, 1, 2, 3, ..., M, ...

For a 0-based cell (r, c), its row-major index is:

index = r * C + c

So the cost is:

cost(r, c) = (index % M) + 1

We need to output the minimum total cost of any legal path.

Core DSA Concepts Involved

• 动态规划

Use a state to represent the best cost to reach a position.

• State Transition

Each current cell can only be reached from at most three neighboring cells in the previous row.

• 滚动数组

The current row depends only on the previous row, so we do not need to store the full R x C DP table.

• 网格路径优化

This is a classic grid DP pattern with local transitions between rows.

Dynamic Programming Idea

Define:

dp[r][j] = minimum total cost to reach row r, column j

The base row is:

dp[0][j] = cost(0, j)

For later rows:

dp[r][j] = cost(r, j) + min(
    dp[r - 1][j - 1],
    dp[r - 1][j],
    dp[r - 1][j + 1]
)

Only valid columns are included.

The final answer is:

answer = min(dp[R - 1][j])

Why Rolling Arrays Work

A full 2D DP table would use:

O(R * C)

space.

But when computing row r, we only need row r - 1.

So we keep two arrays:

• prev[j]: best cost to reach column j in the previous row
• cur[j]: best cost to reach column j in the current row

After finishing one row, we swap them:

prev, cur = cur, prev

The memory becomes:

O(C)

Computing Tile Costs

A common source of mistakes is the cost pattern.

The costs continue across the whole grid in row-major order. They do not restart at 1 for each row.

For example, if C = 4 and M = 5, the grid costs begin:

row 0: 1 2 3 4
row 1: 5 1 2 3
row 2: 4 5 1 2
...

So the first cost in each new row advances by C positions in the repeating sequence.

The code uses:

row_start = ((row_start - 1 + C) % M) + 1

to compute the first tile cost of the next row.

Then each column increases the cost by 1, wrapping back to 1 after M.

Python 解法

# CCC 2025 J5 - Connecting Territories
# Dynamic Programming with rolling arrays
# Time:  O(R * C)
# Space: O(C)

R = int(input())
C = int(input())
M = int(input())

# prev[j] = best cost to reach column j in the previous row
prev = [0] * C
cur = [0] * C

# Row 0 costs: 1, 2, 3, ..., M, 1, 2, ...
v = 1
for j in range(C):
    prev[j] = v
    v += 1
    if v == M + 1:
        v = 1

# row_start is the first tile value in the current row.
# Row 0 starts at 1. Each next row advances by C positions.
row_start = 1

for r in range(1, R):
    row_start = ((row_start - 1 + C) % M) + 1
    v = row_start

    if C == 1:
        # Only one column: must go straight down
        cur[0] = prev[0] + v
    else:
        # First column: can only come from prev[0] or prev[1]
        best = min(prev[0], prev[1])
        cur[0] = best + v

        v += 1
        if v == M + 1:
            v = 1

        # Middle columns
        for j in range(1, C - 1):
            best = min(prev[j - 1], prev[j], prev[j + 1])
            cur[j] = best + v

            v += 1
            if v == M + 1:
                v = 1

        # Last column: can only come from prev[C - 2] or prev[C - 1]
        best = min(prev[C - 2], prev[C - 1])
        cur[C - 1] = best + v

    prev, cur = cur, prev

print(min(prev))

C++ 解法

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

using namespace std;

// CCC 2025 J5 - Connecting Territories
// Dynamic Programming with rolling arrays
// Time:  O(R * C)
// Space: O(C)

int main() {
    int R, C, M;
    cin >> R >> C >> M;

    vector<long long> prev(C, 0), cur(C, 0);

    // Row 0 costs: 1, 2, 3, ..., M, 1, 2, ...
    int v = 1;
    for (int j = 0; j < C; j++) {
        prev[j] = v;
        v++;
        if (v == M + 1) v = 1;
    }

    // row_start is the first tile value in the current row.
    // Row 0 starts at 1. Each next row advances by C positions.
    int row_start = 1;

    for (int r = 1; r < R; r++) {
        row_start = ((row_start - 1 + C) % M) + 1;
        v = row_start;

        if (C == 1) {
            // Only one column: must go straight down
            cur[0] = prev[0] + v;
        } else {
            // First column: can only come from prev[0] or prev[1]
            long long best = min(prev[0], prev[1]);
            cur[0] = best + v;

            v++;
            if (v == M + 1) v = 1;

            // Middle columns
            for (int j = 1; j < C - 1; j++) {
                best = min(prev[j - 1], min(prev[j], prev[j + 1]));
                cur[j] = best + v;

                v++;
                if (v == M + 1) v = 1;
            }

            // Last column: can only come from prev[C - 2] or prev[C - 1]
            best = min(prev[C - 2], prev[C - 1]);
            cur[C - 1] = best + v;
        }

        prev.swap(cur);
    }

    cout << *min_element(prev.begin(), prev.end()) << "\n";
    return 0;
}

复杂度分析

There are R rows and C columns.

Each row computes C states, so the time complexity is:

O(R * C)

We only store two arrays of length C, so the space complexity is:

O(C)

常见错误

• Restarting the tile costs from 1 on every row

The cost sequence continues across the whole grid in row-major order.

• Forgetting the boundary columns

Column 0 cannot use j - 1; column C - 1 cannot use j + 1.

• Forgetting the C == 1 case

With only one column, the path must go straight down.

• Using a full 2D DP table unnecessarily

A 2D DP table works conceptually, but rolling arrays are more memory efficient.

• Using int for the total cost in C++

The total cost may be large. long long is safer.

学习成果

After this problem, students should be able to:

• Recognize a grid path dynamic programming problem
• Use dp[row][col] to represent an optimal value at a position
• Transition from local neighboring states
• Optimize DP memory with rolling arrays
• Handle boundary columns and special cases
• Understand row-major order and repeating tile costs

Review Questions

1. Why does dp[r][j] depend only on the previous row?

1. Why do we need a special case when C == 1?

1. Why should tile costs not restart at 1 for each row?

1. Why can rolling arrays reduce memory from O(R * C) to O(C)?

1. If the path could only move straight down and not diagonally, how would the transition formula change?