2010-01-12
迷路
| 
- 流行りの迷路は嫌いですか？
- dijkstraライブラリのテストを兼ねて
- ぐねぐねした意地悪な道がありうる迷路問題でA*使うのってなんか気が進まない派
- 最短性の証明？とりあえず各辺の長さが1 (>0)でダイクストラなので最短な「はず」だけど、とその程度の認識でお開き
- 結果出力は $$$ より ... の方が可愛くてよくない？
main() {
string maze_[] = {"**************************", // ここのカンマを打ち忘れててSからGに辿り着けなかったorz
"*S* * *",
"* * * * ************* *",
"* * * ************ *",
"* * *",
"************** ***********",
"* *",
"** ***********************",
"* * G *",
"* * *********** * *",
"* * ******* * *",
"* * *",
"**************************" };
vector<string> maze(maze_, maze_ + (sizeof(maze_) / sizeof(maze_[0])));
int rows=sz(maze), cols=sz(maze[0]), ids = rows*cols;
vector<vector<char> > result(rows,vector<char>(cols));
vector<vector<int> > arcs(ids,vector<int>(ids,infty));
int start, goal;
rep(r,rows) rep(c,cols) {
result[r][c] = maze[r][c];
int id = r*cols + c;
if (maze[r][c] != '*') {
if (maze[r][c] == 'S') start = id;
else if (maze[r][c] == 'G') goal = id;
if (1<=c && maze[r][c-1]!='*') {
int jd=id-1;
arcs[id][jd] = arcs[jd][id] = 1;
}
if (c<=cols-2 && maze[r][c+1]!='*') {
int jd=id+1;
arcs[id][jd] = arcs[jd][id] = 1;
}
if (1<=r && maze[r-1][c]!='*') {
int jd=id-cols;
arcs[id][jd] = arcs[jd][id] = 1;
}
if (r<=rows-2 && maze[r+1][c]!='*') {
int jd=id+cols;
arcs[id][jd] = arcs[jd][id] = 1;
}
}
}
list<int> route = dijkstra1(arcs,start,goal).first;
tr(route,it){
int id=*it, r=id/cols, c=id%cols;
if(result[r][c]==' ') result[r][c]='$';
// if(result[r][c]==' ') result[r][c]='.'; // I prefer
}
tr(result,it){
cout << string(all(*it)) << endl;
}
}
Dijkstra + Prim
| 
- 自分のコピペ用。「最短経路の本」より
const int DIJKSTRA_1 = 1;
const int DIJKSTRA = 2;
const int PRIM = 4;
const int infty = INT_MAX;
template <typename T> T infsum(T a, T b){
return (a == infty || b == infty)? infty : (a + b);
}
list<int> follow_predecessor(const vector<int>& predecessor, int start_v, int goal_v)
{
list<int> ans;
for(int v=goal_v; v!=start_v; v=predecessor[v]) ans.push_back(v);
ans.push_back(start_v);
reverse(ans.begin(), ans.end());
return ans;
}
template <typename T> vector<vector<T> > arcs_to_edges(vector<vector<T> > arclength)
{
int N = arclength.size();
vector<vector<T> > edgelength(N,vector<int>(N,infty));
for (int i=0; i<N-1; i++){
for (int j=i+1; j<N; j++){
T a_ij = arclength[i][j], a_ji = arclength[j][i];
edgelength[i][j] = edgelength[j][i] = min(a_ij, a_ji);
}
}
return edgelength;
}
//
// dijkstra__(arclength, start_v[, goal_v])
//
// Input: 弧の長さ arclength[i][j], スタート地点、ゴール地点を与える
// Output: distance[], predecessor[]
//
template <typename T> pair<vector<T>,vector<int> >
dijkstra_prim_core(int algo, const vector<vector<T> >& arclength, int start_v, int goal_v=-1)
{
int N = arclength.size();
set<int> S;
vector<T> distance(N, infty); // inftyは適当な大きな数
vector<int> predecessor(N, -1);
S.insert(start_v);
distance[start_v] = 0;
rep(v,N){
if (v == start_v) continue;
if (arclength[start_v][v] == infty) continue;
distance[v] = arclength[start_v][v];
predecessor[v] = start_v;
}
while (((algo & 1) && !found(S, goal_v)) // 指定されたゴールへ
|| ((algo & 6) && S.size() < N)) { // 各点へ
// find v* from V¥S with distance(v*) = min{distance(v):v from V¥S}
int v_ = -1;
T d_ = infty;
rep(v,N){
if (found(S,v)) continue;
if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
}
if (v_ == -1) break; // たどりつけない...
S.insert(v_);
rep(v,N){ // FOR ALL v from V¥S DO
if (found(S,v)) continue;
T d_; // distance[v]
switch (algo) {
case DIJKSTRA: case DIJKSTRA_1:
d_ = infsum(distance[v_], arclength[v_][v]); break;
case PRIM:
d_ = arclength[v_][v]; break;
}
if (d_ < distance[v]) {
distance[v] = d_;
predecessor[v] = v_;
}
}
}
return make_pair(distance,predecessor);
}
//
// dijkstra1(arclength, start_v, goal_v)
//
// Input: 弧の長さ arclength[i][j], スタート地点、ゴール地点を与える
// Output: スタート地点からゴール地点への経路と距離、のペア
//
template <typename T> pair<list<int>,T>
dijkstra1(vector<vector<T> > arclength, int start_v, int goal_v)
{
pair<vector<T>,vector<int> > res = dijkstra_prim_core(DIJKSTRA_1, arclength, start_v, goal_v);
list<int> lis = follow_predecessor(res.second, start_v, goal_v);
return make_pair(lis, res.first[goal_v]);
}
//
// dijkstra(arclength, start_v)
//
// Input: 弧の長さ arclength[i][j], スタート地点を与える
// Output: スタート地点から各点への経路と距離のペア、のベクタ
//
template <typename T> vector<pair<list<int>,T> >
dijkstra(vector<vector<T> > arclength, int start_v)
{
pair<vector<T>,vector<int> > res = dijkstra_prim_core(DIJKSTRA, arclength, start_v);
int N = arclength.size();
vector<pair<list<int>,T> > ans(N);
rep(v,N){
list<int> lis = follow_predecessor(res.second, start_v, v);
ans[v] = make_pair(lis, res.first[v]);
}
return ans;
}
/////////////
//
// 最小全域木 - Primのアルゴリズム
//
template <typename T> vector<int>
prim(vector<vector<T> > edgelength, int start_v)
{
return dijkstra_prim_core(PRIM, edgelength, start_v).second;
}
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100112