Intermediate.
Put your skills to the test.

Problem summary

Start anywhere in the leftmost column. Move to the next column in the same or an adjacent row. Find the minimum visited-cell sum on reaching the rightmost column.

Constraints

1 < m,n < 1000; entries are positive integers below 100.

Worked example

Input and output for the worked example discussed below.

4 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6

17

Solution analysis

1. Let previous[r] be the cheapest cost reaching row r in the previous column. Initialize it with each first-column value, because the starting row is unrestricted.
2. For each new column, current[r] is its value plus the minimum of previous[r] and any valid previous neighbours r−1,r+1. Compute a fresh array so transitions never reuse the current column.
3. In the sample, column 2 costs become [7,4,14,9]. Continue the same recurrence, then take the minimum over final rows; the full answer is 17. There is no first-row/last-row wrapping.

Why it works

Each legal path to a cell comes from exactly one of its three permitted predecessors. Taking the smallest optimal predecessor cost and adding the cell value gives the optimal cost by induction on columns. Minimizing the final row handles all possible endpoints.

Watch out. Do not update the previous column in place. Starting and ending rows are free choices; row moves are at most one and never wrap.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows;
    int columns;
    cin>>rows>>columns;
    vector<vector<int>>grid(rows,vector<int>(columns));
    for(auto&row:grid){
        for(int&value:row){
            cin>>value;
        }
    }
    vector<int>previous(rows);
    for(int r=0;r<rows;r++){
        previous[r]=grid[r][0];
    }
    for(int c=1;c<columns;c++){
        vector<int>current(rows,numeric_limits<int>::max());
        for(int r=0;r<rows;r++){
            // Read all predecessors from the previous column only.
            for(int offset=-1;offset<=1;offset++){
                int before=r+offset;
                if(before>=0&&before<rows){
                    current[r]=min(current[r],previous[before]+grid[r][c]);
                }
            }
        }
        previous=current;
    }
    cout<<*min_element(previous.begin(),previous.end())<<'\n';
}