#include "wombats.h" #include <bits/stdc++.h> using namespace std; int h[5000][200]; int v[5000][200]; int Hi[5000][200]; int Vi[5000][200]; int r, c; void init(int R, int C, int H[5000][200], int V[5000][200]) { for (int i = 0;i < 5000;i++) { for (int j = 0;j < 200;j++) { h[i][j] = H[i][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) { int y1 = V1, x1 = 0, y2 = V2, x2 = r - 1; priority_queue <array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq; pq.push({0, x1, y1}); int vis[r][c]; for (int i = 0;i < r;i++) { for (int j = 0;j < c;j++) { vis[i][j] = INT_MAX; } } vis[x1][y1] = 0; int ans = INT_MAX; while (!pq.empty()) { int x = pq.top()[1]; int y = pq.top()[2]; int w = pq.top()[0]; //cout << x << " " << y << " " << w << endl; pq.pop(); //x, y -> x, y - 1; if (y > 0 && vis[x][y - 1] > w + h[x][y - 1]) { pq.push({w + h[x][y - 1], x, y - 1}); vis[x][y - 1] = w + h[x][y - 1]; } //x, y -> x, y + 1; if (y < c - 1 && vis[x][y + 1] > w + h[x][y]) { pq.push({w + h[x][y], x, y + 1}); vis[x][y + 1] = w + h[x][y]; } //x, y -> x + 1, y; if (x < r - 1 && vis[x + 1][y] > w + v[x][y]) { pq.push({w + v[x][y], x + 1, y}); vis[x + 1][y] = w + v[x][y]; } } return vis[x2][y2]; }