Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-01-12

迷路

14:44 | 迷路 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 迷路 - naoya_t@topcoder 迷路 - naoya_t@topcoder のブックマークコメント

  • 流行りの迷路は嫌いですか?
  • 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

14:44 | Dijkstra + Prim - naoya_t@topcoder を含むブックマーク はてなブックマーク - Dijkstra + Prim - naoya_t@topcoder Dijkstra + Prim - naoya_t@topcoder のブックマークコメント

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;
}
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100112