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

AOJ1150 Cliff Climbing

解法
拡張グラフにおけるダイクストラを書くだけ。
ポイントは

  • 座標に対応したノード番号のナンバリング(座標としてxとyの2要素持つよりキューに入れるとき都合が良い)
  • ノード番号から座標への変換
  • 左右の足を交互に移動 -> グラフの要素を2倍にする
  • 複数のスタート地点を始めに全てキューに突っ込んでおく。コストのメモも同様に全てのスタート地点を 0 にしておく。

など

他に工夫した所として、
o 小さい判定などはミスを生まない+何度も確認しないようにインライン関数として小分けにした。
o 入力のグリッドに数字と文字が含まれていたので、文字と数字を別に考えたいため char t と int G の両方に入力の値を代入した。
o 通行不可 'X' は G = INF で代用可。コストが負になることはないのでキューに余計な計算が入ることもない。
o 足の踏み方は多分二重ループ回したほうがdx, dyより書きやすい気がする(好み)

反省
サンプルも一度で合って、ACもそのまま一度のサブミットで出せた。
解法が分かれば、元々ミスを生む要素が少ない問題だとは思う。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
#define INF (1<<29)
 
struct State {
  int to, cost;
  bool left;
  bool operator < (const State& s) const {
    return cost > s.cost;
  }
  State(int t, int c, bool l)
    : to(t), cost(c), left(l) {}
};
 
typedef pair<int, int> P;
 
vector<P> start, goal;
char t[61][31];
int G[61][31];
int W, H;
 
inline bool inF(int x, int y) {
  return 0<=x && x<W && 0<=y && y<H;
}
 
/*
  0 1   2   3 ...
  W W+1 W+2 ...
  ...
*/
inline int nidx(int x, int y) {
  return y*W+x;
}
 
inline int posx(int nidx) {
  return nidx % W;
}
 
inline int posy(int nidx) {
  return nidx / W;
}
 
inline bool isout(int i, int j) {
  if(i == -1 && j == 3) return true;
  if(i == +1 && j == 3) return true;
  if(i == -2 && j == 2) return true;
  if(i == +2 && j == 2) return true;
  if(i == -2 && j == 3) return true;
  if(i == +2 && j == 3) return true;
  return false;
}
 
int dijkstra() {
   
  int dist[61][31][2];
  fill(dist[0][0], dist[0][0]+61*31*2, INF);
  priority_queue<State> PQ;
  for(int I=0; I<start.size(); I++) {
    int sx = start[I].first, sy = start[I].second;
    dist[sy][sx][0] = dist[sy][sx][1] = 0;
    PQ.push(State(nidx(sx, sy), 0, false));
    PQ.push(State(nidx(sx, sy), 0, true));
  }
  while(!PQ.empty()) {
    const State st = PQ.top(); PQ.pop();
    const int x = posx(st.to), y = posy(st.to);
    int s = st.left ? -1 : +1;
     
    if(t[y][x] == 'T') return st.cost;
     
    for(int i=-2; i<=2; i++) {
      for(int j=1; j<=3; j++) {
        if(isout(i, j)) continue;
        int nx = x+s*j, ny = y+i;
        if(!inF(nx, ny)) continue;
        if(dist[ny][nx][!st.left] <= st.cost+G[ny][nx]) continue;
        dist[ny][nx][!st.left] = st.cost+G[ny][nx];
        PQ.push(State(nidx(nx, ny), dist[ny][nx][!st.left], !st.left));
      }
    }
  }
   
  return -1;
}
 
int main() {
   
  while(cin >> W >> H && (W|H)) {
    start.clear(); goal.clear();
    for(int i=0; i<H; i++)
      for(int j=0; j<W; j++) {
        cin >> t[i][j];
        if(t[i][j] == 'S') {
          start.push_back(P(j, i));
          G[i][j] = 0;
        }
        else if(t[i][j] == 'T') {
          goal.push_back(P(j, i));
          G[i][j] = 0;
        }
        else if(t[i][j] == 'X'){
          G[i][j] = INF;
        }
        else {
          G[i][j] = t[i][j]-'0';
        }
      }
     
    cout << dijkstra() << endl;
  }
   
  return 0;
}