DouKaku?

再帰の問題例としての迷路問題。 迷路問題は、迷路に対してスタートとゴールを定義し、スタートからゴールまでの道順を探索することである。探索が成功した場合はその経路を表示し、ゴールにたどり着けない場合はその旨を表示することとする。 このような問題では、まず迷路空間をどのように表現するか考慮する必要がある。たとえば格子状を座標と考えて左上（０，０）と考えて右下を（５，５）と表現した場合はスタート（１，１）からゴール（１，４）まで、 （１，１）－（２，１）－（３，１）－（４，１）－４，２）－（４，３）－（３，３）－（２，３）－（２，４）－（１，４） という経路を通ることによってたどり着くと表現できる。 問題の制約 上記のように座標で考えるをわかりやすいが少し趣向を凝らしてリストを用いて迷路空間を表現し探索することを考えてみる。 リストの構成要素は迷路を構成するそれぞれのマス目となる。よって、マス目1つは、以下のような構造体boxで表現できる。構造対boxは自分自身の上下左右のマスを表すポインタと自分自身の状態を保持するためのflagの意味は以下のコメントの通りである。 **(1)** 上記の迷路問題スタートからゴールに辿り着く最短の経路は、次のように表現できる。 ((((((((start->right)->right)->right)->down)->down)->left)->left)->down)->left = goal のように表現できる。 上記の例では、人間の場合は瞬時に最短経路がわかるが、コンピュータは人間のような空間把握能力はないため、逐次滝に経路をたどることによってコールを探すことになる。つまり、ひたすらある方向に進み進めなくなったら違う方向に進むという事を繰り返してゴールを探索する。そのため、必ずしも最短経路を辿ってゴールできるとは限らない。 **(2)** 上記のプログラムを作成してください。 ヒント まずファイルからデータ（迷路空間）を読み込み、迷路空間を構成する。 そのあとに再帰を用いて、スタートからゴールまで探索する。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

図１-
＊＊＊＊＊＊
＊８０００＊
＊＊＊＊０＊
＊＊０００＊
＊９０＊０＊
＊＊＊＊＊＊


**(1)**

struct {
int flag;
struct box *up;
struct box *down;
struct box *right;
struct box *left;
};
struct box *null = (struct box *)NULL;
struct box *start; struct box *goal;


**(2)**

void visit(struct box *b,...) {
①ゴールに到達できない場合は次の処理を行う。
②現在の通路を通過したことを示すフラグを立てる
③上が空いてれば上に移動
④下が空いてれば下に移動
⑤右が空いてれば右に移動
⑥左が空いてれば左に移動
｝