#include "wombats.h"
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <queue>
#include <iostream>
using namespace std;
int R;
int C;
vector<vector<long long> > Hwombats;
vector<vector<long long> > Vwombats;
vector<vector<long long> > escapeCostV2V1;
void fill_escape_costs(){
for (int v1 = 0; v1 < C; v1++){
priority_queue<pair<long long, pair<int, int> > > to_visit;
vector<vector<long long> > costs (R, vector<long long> (C,(R + C) * 2000));
to_visit.push(make_pair(0, make_pair(0, v1)));
while (!to_visit.empty()){
pair<long long, pair<int, int> > current = to_visit.top();
to_visit.pop();
long long d = -current.first;
int r = current.second.first;
int c = current.second.second;
if (costs[r][c] == (R + C) * 2000){
costs[r][c] = d;
if (c != 0){
int nr = r;
int nc = c - 1;
long long nd = d + Hwombats[r][c - 1];
to_visit.push(make_pair(-nd, make_pair(nr, nc)));
}
if (c != C - 1){
int nr = r;
int nc = c + 1;
long long nd = d + Hwombats[r][c];
to_visit.push(make_pair(-nd, make_pair(nr, nc)));
}
if (r != R - 1){
int nr = r + 1;
int nc = c;
long long nd = d + Vwombats[r][c];
to_visit.push(make_pair(-nd, make_pair(nr, nc)));
}
}
}
for (int v2 = 0; v2 < C; v2++){
escapeCostV2V1[v2][v1] = costs[R - 1][v2];
//cout << v1 << ' ' << v2 << ' ' << costs[R - 1][v2] << endl;
}
}
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
R = r;
C = c;
Hwombats = vector<vector<long long> > (R, vector<long long> (C - 1, 0));
Vwombats = vector<vector<long long> > (R - 1, vector<long long> (C, 0));
for (int i = 0; i < R; i++){
for (int j = 0; j < C - 1; j++){
Hwombats[i][j] = H[i][j];
}
}
for (int i = 0; i < R - 1; i++){
for (int j = 0; j < C; j++){
Vwombats[i][j] = V[i][j];
}
}
escapeCostV2V1 = vector<vector<long long> > (C, vector<long long> (C, 0));
fill_escape_costs();
}
void changeH(int P, int Q, int W) {
Hwombats[P][Q] = W;
fill_escape_costs();
}
void changeV(int P, int Q, int W) {
Vwombats[P][Q] = W;
fill_escape_costs();
}
int escape(int V1, int V2) {
return escapeCostV2V1[V2][V1];
}
