(広さ優先探索第一課)迷宮の最短経路-BFS
(N,M<=100)
サンプル入力:
10 10
#
S
#
#
#
#
#
#
.
#
.
.
.
.
.
.
#
.
.
#
.
#
.
#
#
.
#
#
.
#
.
#
.
.
.
.
.
.
.
.
#
#
.
#
#
.
#
#
#
#
.
.
.
.
#
.
.
.
.
#
.
#
#
#
#
#
#
#
.
#
.
.
.
.
#
.
.
.
.
.
.
#
#
#
#
.
#
#
#
.
.
.
.
.
#
.
.
.
G
#
サンプル出力:
22
この問題と解法はいずれも『チャレンジプログラミングコンテスト(第2版)』34ページ-36ページから来ている.
個人的にはこの例題は広さ優先検索がどのようにキューと先に出るかをよく表現していると思います(FIFO)の考え方が結びついているのは,ある状態を取得した後に達成できるすべての状態を取得してキューに入れることにより,キュー自体の特性によりキューに先に加わる状態が常に先に処理されることで,常に遷移回数の少ない状態を分析処理し,言い換えれば常にこの状態を取得することが目的となる.の木の中で根に近いノード、あるいはいつも検索木の広さをできるだけ増加させます.
この問題では、開始点から終了点までの最短パスを見つけることは、キューを構築するプロセスです.
1.始点からキューに入れ、距離を0に設定
2.キューの先頭から位置を取り出し、その位置から到達可能な位置をキューに入れ、その位置の距離を前の位置の距離に1を加算する
3.ループ2がキューの先頭から取り出されるまで終了します.これは、パスが見つかったことを示しています.
この過程において,各処理位置に対応する距離は厳密に増加することに注意し,終点が見つかると,その時の距離が最短距離となる.
同様にこの理由に基づいて,移動可能な位置を探索するために用いられる判断条件は,壁に触れず境界を超えないだけでなく,もう1つは到達していないことである.この位置に到達した場合,これはすでにより短い経路がこの位置に到達していることを示しているため,今回この位置に到達した経路はより悪く,より良い最終解を得ることは不可能である.
#include
#include
#include
using namespace std;
const int MAX_N = 100;
const int MAX_M = 100;
const int INF = 0x3f3f3f3f;
typedef pair P;
char maze[MAX_N][MAX_M + 1];
int N, M;
int sx, sy; //
int gx, gy; //
int d[MAX_N][MAX_M];//
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // x y
void bfs()
{
queue que;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
d[i][j] = INF; // INF
que.push(P(sx, sy));
d[sx][sy] = 0; // 0，
while (que.size()) // ，
{
P p = que.front(); que.pop();//
if(p.first == gx&&p.second == gy) break; //
for (int i = 0; i < 4; i++)
{
int nx = p.first + dx[i];
int ny = p.second + dy[i];//
//
if (0 <= nx&&nx < N
&& 0 <= ny&&ny < M
&&maze[nx][ny] != '#'
&&d[nx][ny] == INF)// ， ，
{
que.push(P(nx, ny)); // ，
d[nx][ny] = d[p.first][p.second] + 1;
}
}
}
}
int main()
{
scanf("%d %d",&N,&M);
for (int n = 0; n < N; n++)
scanf("%s",&maze[n]);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
if (maze[i][j] == 'S')
{
sx = i; sy = j;
}
if (maze[i][j] == 'G')
{
gx = i; gy = j;
}
}
bfs();
printf("%d
",d[gx][gy]);
return 0;
}