ホームに戻る
迷路最短距離

// 最大 50x50 の迷路で2点間の最短距離を得る。
// 壁を # で定義し、床はそれ以外とする。
// 幅優先探索でメモ化を使用している。
// 以下のような迷路図と、幅 w、高さ h を要する。

// "..#."
// "#.#."
// "...."

int w,h;
vector<string> m;
int memo[50][50];

int f(int sy, int sx, int gy, int gx){
  int dy[4] = {-1,0,0,1};
  int dx[4] = {0,-1,1,0};

  memset(memo,0,sizeof(memo));

  memo[sy][sx] = 1;

  queue<int> q1,q2,q3;
  q1.push(sy);
  q2.push(sx);
  q3.push(0);

  while(!q1.empty()){
    int y = q1.front();
    int x = q2.front();
    int c = q3.front();
    q1.pop();
    q2.pop();
    q3.pop();

    if(y == gy && x == gx){
      return c;
    }

    for(int t = 0; t < 4; t++){
      int y1 = y + dy[t];
      int x1 = x + dx[t];
      if(y1 < 0 || y1 >= h)continue;
      if(x1 < 0 || x1 >= w)continue;
      if(m[y1][x1] == '#')continue;
      if(memo[y1][x1] == 1)continue;
      memo[y1][x1] = 1;
      q1.push(y1);
      q2.push(x1);
      q3.push(c+1);
    }
  }
  return -1;
}

inserted by FC2 system