「AOJ1156 Twirling Robot」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*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は < でなく > を定義する必要がある
====
補足
+sort関数などはgreaterを指定すると降順に並ぶが、priority_queueはgreaterを指定すると最小を取り出すようになる。sort関数のイメージに惑わされやすいので注意）
+構造体でなく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<State>となる）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 is not empty
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
||<
*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は < でなく > を定義する必要がある
====
補足
+sort関数などはgreaterを指定すると降順に並ぶが、priority_queueはgreaterを指定すると最小を取り出すようになる。sort関数のイメージに惑わされやすいので注意）
+構造体でなく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<State>となる）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
||<
