グラフ問題で経路の探索の方法として、深さ優先探索（DFS:Depth First Search）と幅優先探索（BFS:Breadth First Search）があります。dfsは考えられる経路をすべて探索していくのに対して、bfsは最短経路を辿っていきます。
縦Hマス×横Wマスの中で、上下左右の接したマスであって、通ったことがないマスに移動していくことを繰り返しながら移動していく場合を考えます。
dfs（深さ優先探索）
すべての経路（の中で、条件を満たす経路）を調べる。以下では、経路が目的地に到達したら経路を出力するようにしている。
/* area size = h x w */
/* s & t...point in area, in case h=2 & w=4 0 1 2 3 */
/* 4 5 6 7 */
/* d : length of path */
/* p : path */
/* seen : 0 = not yet seen, 1 = already seen */
void dfs(int h, int w, int s, int t, int d, int p[], int seen[]) {
p[d] = s; /* add current point to path */
seen[s] = 1; /* check as seen */
if (s == t) { /* if current point = target point */
for (int i = 0; i <= d; i++) /* print path from start to target */
printf("(%d,%d) ", p[i] / w, p[i] % w);
printf("\n");
return;
}
int x = s / w; /* x-y value of current point */
int y = s % w;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nx = x + dh[i]; /* point next to current point */
int ny = y + dw[i];
if (nx < 0 || nx > h-1 || ny < 0 || ny > w-1)
/* if point out of area */
continue;
if (seen[nx * w + ny]) /* if point already seen */
continue;
dfs(h, w, nx * w + ny, t, d+1, p, seen);
seen[nx * w + ny] = 0; /* clear seen check */
}
}
例えば、H×Wのマスがあるとき、左上隅から右下隅まで行く行き方が何通りあるかを調べるには、
int p[h*w];
int seen[h*w];
for (int i = 0; i < h*w; i++) seen[0];
dfs(h, w, 0, h*w-1, 0, p, seen);
とすると、すべての経路を出力してくれる。3×3の場合は、
(0,0) (1,0) (2,0) (2,1) (2,2)
(0,0) (1,0) (2,0) (2,1) (1,1) (1,2) (2,2)
(0,0) (1,0) (2,0) (2,1) (1,1) (0,1) (0,2) (1,2) (2,2)
(0,0) (1,0) (1,1) (2,1) (2,2)
(0,0) (1,0) (1,1) (1,2) (2,2)
(0,0) (1,0) (1,1) (0,1) (0,2) (1,2) (2,2)
(0,0) (0,1) (1,1) (2,1) (2,2)
(0,0) (0,1) (1,1) (1,2) (2,2)
(0,0) (0,1) (1,1) (1,0) (2,0) (2,1) (2,2)
(0,0) (0,1) (0,2) (1,2) (2,2)
(0,0) (0,1) (0,2) (1,2) (1,1) (2,1) (2,2)
(0,0) (0,1) (0,2) (1,2) (1,1) (1,0) (2,0) (2,1) (2,2)
のような12通りの経路がある（各点は(縦座標、横座標)）。
bfs（幅優先探索）
最短距離を調べる。幅優先探索の場合queueを使う。C言語ではqueueは標準で実装されていないので、行列で実装している。
/* area size = h x w */
/* s & t...point in area, in case h=2 & w=4 0 1 2 3 */
/* 4 5 6 7 */
/* seen : number of points from start point */
void bfs(int h, int w, int s, int t, int seen[]) {
const int qmax = 20; /* max queue size */
int que[qmax]; /* queue array */
int qs = 0, qe = 0; /* qs: queue top, qe: queue tail */
que[qe] = s; /* add start to queue */
qe = (qe + 1) % qmax; /* queue tail to next */
while (qs != qe) { /* queue not empty */
int p = que[qs]; /* from queue top */
qs = (qs + 1) % qmax; /* queue top to next */
int x = p / w; /* x-y value of current point */
int y = p % w;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nx = x + dh[i]; /* point next to current point */
int ny = y + dw[i];
if (nx < 0 || nx > h-1 || ny < 0 || ny > w-1)
/* if point out of area */
continue;
if (seen[nx * w + ny] >= 0) /* if point already seen */
continue;
seen[nx * w + ny] = seen[p] + 1; /* number of points to next */
que[qe] = nx * w + ny; /* add queue */
qe = (qe + 1) % qmax; /* q tail to next */
}
}
}
例えば、3x3の場合、
int seen[h*w];
for (int i = 0; i < h*w; i++) seen[i] = -1;
seen[0] = 0;
bfs(h, w, 0, h*w-1, seen);
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
printf("%d", seen[i*w + j]);
if (j < w-1) printf(" ");
else printf("\n");
}
}
とすると、
0 1 2
1 2 3
2 3 4
と、左上隅から各点の最短経路長が記録され、右下隅までの最短経路長は4である。