AOJ 1150 崖登り (ICPC 国内予選 2007 D) (400 点)

難しくはないけど、実装が少し辛い。

• 問題へのリンク

問題概要

(略) 基本的にはグリッド上を移動していく最短路問題だけど、色々制約が付随している

考えたこと

一目見て Dijkstra 法が使えるとわかるけど、面倒...
ポイントになりそうなのは、「左足」を動かそうとしているときに、「左足」が今どこにあるかを覚えておく必要はない辺りかなと思う。

このことを意識すると、状態量は (x 座標, y 座標, 左足か右足か) の 3 次元で済ませることができる。

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1<<29;

int N, M;
vector<vector<int> > fi;
typedef pair<int,int> pint;
typedef pair<pint,bool> state;

int dp[65][35][2]; // 0: 左足、1: 右足

int main() {
  while (cin >> M >> N) {
    if (N == 0) break;
    fi.clear(); fi.resize(N);
    vector<pint> starts;
    set<pint> goals;
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
        char c; cin >> c;
        int time = 0;
        if (c == 'X') time = -1;
        else if (c == 'S') starts.push_back(pint(i, j)), time = 0;
        else if (c == 'T') goals.insert(pint(i, j)), time = 0;
        else time = (int)(c - '0');
        fi[i].push_back(time);
      }
    }
    int res = INF;
    priority_queue<pair<int,state>, vector<pair<int,state> >, greater<pair<int,state> > > que;
    for (int i = 0; i < 65; ++i) for (int j = 0; j < 35; ++j) {
        for (int it = 0; it < 2; ++it)
          dp[i][j][it] = INF;
      }
    for (auto p : starts) {
      for (int it = 0; it < 2; ++it) {
        dp[p.first][p.second][it] = 0;
        que.push(make_pair(0, state(p,it)));
      }
    }
    while (!que.empty()) {
      auto cur = que.top(); que.pop();
      int curdist = cur.first;
      pint p = cur.second.first;
      int lr = cur.second.second;
      if (goals.count(p)) chmin(res, curdist);
      if (curdist > dp[p.first][p.second][lr]) continue;
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
          if (lr == 0 && j <= p.second) continue;
          if (lr == 1 && j >= p.second) continue;
          if (abs(i - p.first) + abs(j - p.second) > 3) continue;
          if (fi[i][j] == -1) continue;
          if (chmin(dp[i][j][1-lr], curdist + fi[i][j])) {
            que.push(make_pair(dp[i][j][1-lr], state(pint(i,j), 1-lr)));
          }
        }
      }
    }
    if (res < INF) cout << res << endl;
    else cout << -1 << endl;
  }
}