ソースコード
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int64 INF = 1LL << 58;
const int vy[] = {1, 0, -1, 0};
const int vx[] = {0, 1, 0, -1};
int main()
{
int H, W;
int gy, gx;
int Y[1000], X[1000];
int yl, yr, xl, xr;
cin >> H >> W;
cin >> gy >> gx;
--gy, --gx;
for(int i = 0; i < H; i++) cin >> Y[i];
for(int i = 0; i < W; i++) cin >> X[i];
cin >> yl >> yr >> xl >> xr;
--yl, --yr, --xl, --xr;
int64 dp[1000000];
fill_n(dp, 1000000, INF);
dp[0] = 0;
typedef pair< int64, int > Pi;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
que.emplace(0, 0);
dp[0] = 0;
while(!que.empty()) {
auto p = que.top();
que.pop();
if(p.first > dp[p.second]) continue;
int y = p.second / 1000, x = p.second % 1000;
if(gy == y && gx == x) {
cout << p.first << endl;
return (0);
}
for(int i = 0; i < 4; i++) {
int ny = y + vy[i], nx = x + vx[i];
if(ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
if(yl <= ny && ny <= yr && xl <= nx && nx <= xr) continue;
int64 cost = p.first + (i % 2 == 1 ? Y[y] : X[x]);
int nidx = ny * 1000 + nx;
if(cost >= dp[nidx]) continue;
dp[nidx] = cost;
que.emplace(cost, nidx);
}
}
cout << -1 << endl;
}