読者です 読者をやめる 読者になる 読者になる

AOJ 1156: Twirling Robot

解法

位置・状態を頂点にしたグラフでダイクストラ

類題
kenkoooo.hatenablog.com

コード

#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]; }

  // private:
  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) {  // u,r,d,l
    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;
  }
  // for (int k = 0; k < 4; ++k) {
  //   for (int i = 0; i < h; ++i) {
  //     for (int j = 0; j < w; ++j) {
  //       cout << dijkstra.distances[i * w + j + WH * k] << " ";
  //     }
  //     cout << endl;
  //   }
  //   cout << endl;
  // }
  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);
  }
}