Among the four given moves, if we didn’t have the last move, we can solve the problem in a total of \(O(RC \log (RC))\) time with Dijkstra’s algorithm. How can we handle the last move?
If the cost of the move was \(i\) instead of \(1+i\), we can add an edge of cost \(1\) from \((r, c)\) to \((r-1,c)\) so that we can take into account the move of cost \(i\).
As for cost \(1+i\), the following procedures of adding edges are effective:

• Double each vertex. Now we assume we have two kinds of vertices, normal \((r, c)\) and intermediate \((r, c)\).
• Add an edge of cost \(1\) from normal \((r, c)\) to intermediate \((r, c)\)
• Add an edge of cost \(1\) from intermediate \((r, c)\) to intermediate \((r-1, c)\)
• Add an edge of cost \(0\) from intermediate \((r, c)\) to normal \((r, c)\)

Now we can see that the moves can be represented as a graph with \(O(RC)\) number of vertices and \(O(RC)\) number of edges, thus we can solve the problem in a total of \(O(RC \log (RC))\) with Dijkstra’s algorithm.

Sample Code (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
bool chmin(int& a, int b){ if(a > b){ a = b; return 1; } return 0; }

int main(){
    int R, C;
    cin >> R >> C;
    vector A(R, vector<int>(C - 1)), B(R - 1, vector<int>(C));
    for(auto& a : A) for(int& i : a) cin >> i;
    for(auto& b : B) for(int& i : b) cin >> i;
    vector cost(2, vector(R, vector(C, 0x3fffffff)));
    priority_queue q(greater<>{}, vector<tuple<int, int, int, int>>{});
    auto update = [&](int f, int r, int c, int x){
        if(chmin(cost[f][r][c], x)) q.emplace(x, f, r, c);
    };
    update(0, 0, 0, 0);
    while(q.size()){
        auto [x, f, r, c] = q.top();
        q.pop();
        if(cost[f][r][c] != x) continue;
        if(f){
            update(0, r, c, x);
            if(r) update(1, r - 1, c, x + 1);
        }
        else{
            update(1, r, c, x + 1);
            if(r + 1 < R) update(0, r + 1, c, x + B[r][c]);
            if(c) update(0, r, c - 1, x + A[r][c - 1]);
            if(c + 1 < C) update(0, r, c + 1, x + A[r][c]);
        }
    }
    cout << cost[0].back().back() << endl;
}

Sample Code (Python)

from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix

R, C = map(int, input().split())
data = []
row = []
column = []
for i in range(R):
    a = list(map(int, input().split()))
    for j in range(C - 1):
        x = i * C + j
        y = i * C + j + 1
        row += [x, y]
        column += [y, x]
        data += [a[j], a[j]]
for i in range(R - 1):
    a = list(map(int, input().split()))
    for j in range(C):
        x = i * C + j
        y = i * C + j + C
        row += [x, y + R * C]
        column += [y, x + R * C]
        data += [a[j], 1]
for i in range(R):
    for j in range(C):
        x = i * C + j
        y = x + R * C
        row += [x, y]
        column += [y, x]
        data += [1, 0]
g = csr_matrix((data, (row, column)))
print(int(shortest_path(g, indices=0)[R * C - 1]))