naoya_t@topcoder

迷路

14:44 |

• 流行りの迷路は嫌いですか？
  • see http://okajima.air-nifty.com/b/2010/01/post-abc6.html
• 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;
  }
}