ソースコード
#include "iostream"
#include "climits"
#include "queue"
#include "functional"
using namespace std;
int main() {
int H, W;
cin >> H >> W;
int y, x;
cin >> y >> x;
int cost_y[1001] = {};
int cost_x[1001] = {};
for (int j = 1; j <= H; j++) {
cin >> cost_y[j];
}
for (int j = 1; j <= W; j++) {
cin >> cost_x[j];
}
int yl, yr, xl, xr;
cin >> yl >> yr >> xl >> xr;
int dis[1002][1002] = {};
bool flag[1002][1002] = {};
for (int j = 1; j <= H; j++) {
for (int k = 1; k <= W; k++) {
dis[j][k] = INT_MAX;
flag[j][k] = true;
}
}
for (int j = yl; j <= yr; j++) {
for (int k = xl; k <= xr; k++) {
flag[j][k] = false;
}
}
priority_queue < pair<int, pair<int, int>>, vector < pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>Q;
Q.push({ 0,{ 1,1 } });
while (!Q.empty()) {
int cy, cx, c;
c = Q.top().first;
cy = Q.top().second.first;
cx = Q.top().second.second;
Q.pop();
if (dis[cy][cx] <= c)continue;
dis[cy][cx] = c;
if (cy == y&&cx == x)break;
if (flag[cy + 1][cx]) {
if (c + cost_x[cx] < dis[cy + 1][cx]) {
dis[cy + 1][cx] = c + cost_x[cx];
Q.push({ c + cost_x[cx] ,{ cy + 1,cx } });
}
}
if (flag[cy - 1][cx]) {
if (c + cost_x[cx] < dis[cy - 1][cx]) {
dis[cy - 1][cx] = c + cost_x[cx];
Q.push({ c + cost_x[cx] ,{ cy - 1,cx } });
}
}
if (flag[cy][cx + 1]) {
if (c + cost_y[cy] < dis[cy][cx + 1]) {
dis[cy][cx + 1] = c + cost_y[cy];
Q.push({ c + cost_y[cy] ,{ cy,cx + 1 } });
}
}
if (flag[cy][cx - 1]) {
if (c + cost_y[cy] < dis[cy][cx - 1]) {
dis[cy][cx + 1] = c + cost_y[cy];
Q.push({ c + cost_y[cy] ,{ cy,cx - 1 } });
}
}
}
if (dis[y][x] == INT_MAX) {
cout << "-1\n";
}
else {
cout << dis[y][x] << endl;
}
return 0;
}