AOJ1156 Twirling Robot


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

AOJ1156 Twirling Robot

サイト

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156

解説

コストが0, 若しくはc0, c1, c2, c3 で与えられるのでダイクストラする

BFSは一種のダイクストラで、普通各ノード間のコストが1のときをいう

ここで座標x, y, 方向, スタート地点からのコストの4つの要素を状態として持つ以下の様な構造体Stateを考える

struct State {
  int x, y, d, cost;
  State() {}
  State(int x, int y, int d, int cost) : x(x), y(y), d(d), cost(cost) {}
  ...
};

これをpriority_queueに入れて解く。

(今回のようにノードの情報の要素が多いとき頂点が増えるので O(|V|^2) の ダイクストラを使うと失敗することが多い。よってO(|E|log|V|)のpriority_queueを使ったダイクストラを使うのが懸命)

但し構造体Stateを定義した場合、比較演算子が定義されてないのでoperatorを使って定義しなければならない

また、priority_queueで最小コストを持つStateを取り出すためはgreaterを指定する必要がある。よってoperatorは < でなく > を定義する必要がある


補足

  1. sort関数などはgreaterを指定すると降順に並ぶが、priority_queueはgreaterを指定すると最小を取り出すようになる。sort関数のイメージに惑わされやすいので注意)
  2. 構造体でなくpairで状態を持つならoperatorを定義する必要はない

以上より構造体Stateは以下のように記述できる

struct State {
  int x, y, d, cost;
  State() {}
  State(int x, int y, int d, int cost) : x(x), y(y), d(d), cost(cost) {}
  bool operator > (const State &s) const {
    return cost > s.cost;
  }
};

priority_queueは通常コンテナの指定を省略できるが、priority_queueにgreaterなどを指定するときはコンテナを指定しないといけない。priority_queueはデフォルトでvectorがコンテナになっているので

priority_queue<State, vector<State>, greater<State> > Q;

としておけば良い

ちなみにpriority_queueにgreaterを指定しないで(つまり自動でlessとなる)operatorの内容を弄って

bool operator < ( const &State s ) {
  return cost > s.cost;
}

とすれば同様にpriority_queueから最小のコストを持つ状態を取り出せるようになる


operatorについて蛇足

operatorの書き方は、struct{...};の外に出して

struct {...};
bool operator>(const State &s1, const State &s2) const {
  return s1.cost>s2.cost;
}

としてもよい。構造体やクラス内に埋め込む場合、const State &s1が自分自身を指すため省略できると考えてみると分かりやすいかも知れない


以下、擬似コード

Dijkstra
  PRIORITY QUEUE <State> Q
  初期化処理
  スタート地点のコスト = 0
  ENQUEUE(Q, s)
  while Q が空でない
    u = DEQUEUE(Q)
    IF 既に求めたコストの方が小さい CONTINUE
    IF ゴール地点 RETURN u.cost
    FOR 現在地から四方向
      v = u
      v.cost += 与えられたグラフの情報と向きが同じかどうか判定してコストを追加
      vの位置や向きを更新
      IF コスト更新出来るか
        ENQUEUE(Q, t)
        コスト更新
      END IF
    END FOR
  END WHILE
RETURN INF