#include "wombats.h"
#include<stdlib.h>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> P;
typedef pair<int,P> Pi;
int H[5000][200],V[5000][200];
int R,C;
bool check[5000][200];
//37point;
void init(int R, int C, int H_[5000][200], int V_[5000][200]){
int i,j;
for(i=0;i<R;i++)for(j=0;j<C-1;j++)H[i][j]=H_[i][j];
for(i=0;i<R-1;i++)for(j=0;j<C;j++)V[i][j]=V_[i][j];
::R=R;
::C=C;
}
void changeH(int P, int Q, int W){
H[P][Q]=W;
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
}
int escape(int V1, int V2) {
priority_queue <Pi,vector<Pi>,greater<Pi> > pq;
int i,j;
for(i=0;i<R;i++)for(j=0;j<C;j++)check[i][j]=0;
pq.push(Pi(0,P(0,V1)));
while(!pq.empty()){
Pi t=pq.top();
pq.pop();
if(check[t.Y.X][t.Y.Y])continue;
check[t.Y.X][t.Y.Y]=1;
if(t.Y.X == R-1 && t.Y.Y == V2)return t.X;
if(t.Y.Y!=C-1 && !check[t.Y.X][t.Y.Y+1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y],P(t.Y.X,t.Y.Y+1)));
if(t.Y.Y && !check[t.Y.X][t.Y.Y-1])pq.push(Pi(t.X+H[t.Y.X][t.Y.Y-1],P(t.Y.X,t.Y.Y-1)));
if(t.Y.X!=R-1 && !check[t.Y.X+1][t.Y.Y])pq.push(Pi(t.X+V[t.Y.X][t.Y.Y],P(t.Y.X+1,t.Y.Y)));
}
}
