2025 J5 - Connecting Territories

1// By Daniel Zhang, Pinetree Secondary
2
3#include <bits/stdc++.h>
4
5using namespace std;
6
7int r, c, m;
8
9int grid(int row, int col) {
10    return (row * c + col) % m + 1;
11}
12
13int main() {
14    cin >> r >> c >> m;
15    
16    vector<int> prev(c, 0), curr(c, 0);
17
18    for (int i = 0; i < c; i++) {
19        prev[i] = grid(0, i);
20    }
21
22    for (int i = 1; i < r; i++) {
23        curr[0] = min(prev[0], prev[1]) + grid(i, 0);
24        curr[c - 1] = min(prev[c - 2], prev[c - 1]) + grid(i, c - 1);
25
26        for (int j = 1; j < c - 1; j++) {
27            curr[j] = min({prev[j - 1], prev[j], prev[j + 1]}) + grid(i, j);
28        }
29
30        swap(prev, curr);
31    }
32
33    cout << *min_element(prev.begin(), prev.end()) << endl;
34}