コード
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;
typedef long long ll;
template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
if (!v.empty()) {
out << '[';
std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
out << "\b\b]";
}
return out;
}
template <typename T>
class Dijkstra {
public:
Dijkstra(int vertex_num) {
this->vertex_num = vertex_num;
edges = vector<vector<tuple<int, T>>>(vertex_num);
distances = vector<T>(vertex_num);
}
void addEdge(int from, int dest, T cost) {
edges[from].push_back(make_tuple(dest, cost));
}
void update(int source) {
for (int i = 0; i < vertex_num; ++i) distances[i] = -1;
distances[source] = 0;
priority_queue<tuple<T, int>, vector<tuple<T, int>>, greater<tuple<T, int>>>
q;
q.push(make_tuple(0, source));
while (!q.empty()) {
int vertex = get<1>(q.top());
T distance = get<0>(q.top());
q.pop();
if (distances[vertex] < distance) continue;
for (auto e : edges[vertex]) {
int next_vertex = get<0>(e);
T next_distance = get<1>(e) + distance;
if (distances[next_vertex] == -1 ||
next_distance < distances[next_vertex]) {
distances[next_vertex] = next_distance;
q.push(make_tuple(next_distance, next_vertex));
}
}
}
}
T getDistance(int vertex) { return distances[vertex]; }
int vertex_num;
vector<vector<tuple<int, T>>> edges;
vector<T> distances;
Dijkstra() {}
};
void solve(int w, int h, vector<vector<int>>& board, vector<int> c) {
Dijkstra<int> dijkstra(w * h * 4);
int WH = w * h;
for (int k = 0; k < 4; ++k) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
vector<int> cost = c;
if (board[i][j] != 4) cost[board[i][j]] = 0;
int v = w * i + j;
int u = i > 0 ? v - w : -1;
int r = j < w - 1 ? v + 1 + WH : -1;
int d = i < h - 1 ? v + w + 2 * WH : -1;
int l = j > 0 ? v - 1 + 3 * WH : -1;
int straight = -1, right = -1, back = -1, left = -1;
if (k == 0) {
if (u >= 0) straight = u;
if (r >= 0) right = r;
if (d >= 0) back = d;
if (l >= 0) left = l;
} else if (k == 1) {
if (u >= 0) left = u;
if (r >= 0) straight = r;
if (d >= 0) right = d;
if (l >= 0) back = l;
} else if (k == 2) {
if (u >= 0) back = u;
if (r >= 0) left = r;
if (d >= 0) straight = d;
if (l >= 0) right = l;
} else {
if (u >= 0) right = u;
if (r >= 0) back = r;
if (d >= 0) left = d;
if (l >= 0) straight = l;
}
if (straight >= 0) dijkstra.addEdge(v + k * WH, straight, cost[0]);
if (right >= 0) dijkstra.addEdge(v + k * WH, right, cost[1]);
if (back >= 0) dijkstra.addEdge(v + k * WH, back, cost[2]);
if (left >= 0) dijkstra.addEdge(v + k * WH, left, cost[3]);
}
}
}
int start = WH * 1;
dijkstra.update(start);
int ans = 1000000000;
for (int i = 0; i < 4; ++i) {
int goal = h * w - 1 + WH * i;
int cost = dijkstra.getDistance(goal);
if (cost >= 0 && cost < ans) ans = cost;
}
cout << ans << endl;
}
int main() {
while (true) {
int w, h;
cin >> w >> h;
if (w == 0) break;
vector<vector<int>> board(h, vector<int>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> board[i][j];
}
}
vector<int> c(4);
for (int i = 0; i < 4; ++i) cin >> c[i];
solve(w, h, board, c);
}
}
