ホームに戻る
迷路最短距離
// 最大 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;
}