再起を使って迷路を解くプログラムを作りたいのですが

質問

map[7][7]={{2,2,2,2,2,2,2},
{2,3,0,0,0,0,2},
{2,2,0,2,2,0,2},
{2,0,0,0,0,2,2},
{2,0,2,0,2,0,2},
{2,2,0,0,0,4,2},
{2,2,2,2,2,2,2}};
２が壁０が道３がスタート４がゴール
の配列で迷路を解く、プログラムを作りたいのですが
再起処理関数の中を、どう書いたらいいのかいまいちわかりません。
誰か教えてください。お願いします

回答No.3

BLUEPIXY · ベストアンサー

プログラムの一例
経路が１つしかない場合は、とりあえずこれでうまくいくと思う。
見つかった経路は、ゴールからスタートに表示されます。
//-------------------------------------------------------------
//２が壁０が道３がスタート４がゴールの配列で迷路を解く
#include <stdio.h>

#define SIZE 7
#define ROAD 0
#define WALL 2
#define START 3
#define GOAL 4

int Map[SIZE][SIZE]={
{WALL ,WALL ,WALL ,WALL ,WALL ,WALL ,WALL },
{WALL ,START,ROAD ,ROAD ,ROAD ,ROAD ,WALL },
{WALL ,WALL ,ROAD ,WALL ,WALL ,ROAD ,WALL },
{WALL ,ROAD ,ROAD ,ROAD ,ROAD ,WALL ,WALL },
{WALL ,ROAD ,WALL ,ROAD ,WALL ,ROAD ,WALL },
{WALL ,WALL ,ROAD ,ROAD ,ROAD ,GOAL ,WALL },
{WALL ,WALL ,WALL ,WALL ,WALL ,WALL ,WALL }};

typedef struct position {
int x;
int y;
} POSITION;

POSITION dir[4]={
{0 ,-1}, //上
{0 , 1}, //下
{-1, 0}, //左
{ 1, 0}};//右

#define FIND 1
#define NOTFIND 0
int check(POSITION base, POSITION diff, POSITION old){
//ベースの位置を基準に探せと指示された場所がゴールでない場合北方向以外の４方向を調べる
POSITION wk;
wk.x=base.x+diff.x;
wk.y=base.y+diff.y;
if(wk.x==old.x && wk.y==old.y){
return NOTFIND;//既に来た所を探してもムダ
}
if(Map[wk.y][wk.x]==GOAL){
printf("GOAL(%d,%d)",wk.x, wk.y);
return FIND;
}
if(Map[wk.y][wk.x]==ROAD){
int i;
for(i=0;i<4;i++){
if(FIND==check(wk, dir[i], base)){
printf("(%d,%d)",wk.x, wk.y);
return FIND;
}
}
}
return NOTFIND;
}

int main(void){
POSITION start;
int i,j;

for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
if(Map[i][j]==3){
start.x=j;
start.y=i;
goto start_find;
}
}
}
printf("開始位置が設定されていません");
return -1;
start_find:
for(i=0;i<4;i++){
if(FIND==check(start, dir[i], start)){
printf("(%d,%d)START\n",start.x,start.y);
return FIND;
}
}
printf("経路が見つかりません");
return NOTFIND;
}

回答No.2

xcrOSgS2wY

では、1歩だけ進むプログラム（関数）をまず目標にしてみましょう。

現在の位置（座標）を引数で受け取り、

・現在の位置（座標）
・進むことのできる位置（座標）

を表示する関数を作ってみてください。

補足

壁に当たったときに次の道を探すにはどうしたらいいですか。

回答No.1

xcrOSgS2wY

その質問だけでは、全部作ってくださいと言っているのと変わりありません。どこまで自力でできて、何ができないのかを書いてください。

再帰を使わなければできますか？

ゴールまでたどり着かないにしても、1歩だけ進むプログラムなら作れますか？

補足

１歩進んだ時に、次に進む場所の探し方の部分がわからないので
そこの部分をお願いします。