\(4\) 種類の移動のうち、一番下の移動がなければ、Dijkstra 法によって時間計算量 \(O(RC \log (RC))\) で解くことができます。そこで、この移動をうまく扱うことを考えます。
もし、移動のコストが \(1+i\) ではなく \(i\) であれば、\((r, c)\) から \((r-1,c)\) へコスト \(1\) の辺を張ることによってコスト \(i\) の移動を実現できます。
コスト \(1+i\) の場合は以下のように辺を張れば良いです。

• 頂点を \(2\) 倍し、通常の \((r, c)\) と移動中の \((r, c)\) の \(2\) 種類を用意する。
• 通常の \((r, c)\) から移動中の \((r, c)\) へコスト \(1\) の辺を張る
• 移動中の \((r, c)\) から移動中の \((r-1, c)\) へコスト \(1\) の辺を張る
• 移動中の \((r, c)\) から通常の \((r, c)\) へコスト \(0\) の辺を張る

これより、\(O(RC)\) 頂点 \(O(RC)\) 辺のグラフで移動が表現できるので、Dijkstra 法によって時間計算量 \(O(RC \log (RC))\) でこの問題を解くことができます。

回答例 (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;
}

回答例 (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]))