やりかたがわからない

⇒のところから処理に積んでいてわからないです。

アルゴリズム的には、右見て前行く。左もいけない。など方向で判定していくのだと思いますが。。。



結果は、ランダムなSからGまで・をたどっていくようにしたいです。
最短でなくて大丈夫です。
実行方法は　aa.c a.c
書き換えるのはa.cの⇒から
よろしくお願いします。


G■■■■■■■
■・■　　　　　■
■・■　　■　　■
■・■　　　　　■
■・　　　　　　■
■・・・・・・・■
■■■■■■■S■


-----a.h----------------------------
#define W 11
#define H 15

#define PASS 0
#define WALL 1
#define START 2
#define GOAL 4
#define TRACK 8

#define TRUE 1
#define FALSE 0

void print_maze(int maze[H][W]);

void create_maze(int maze[H][W]);
int to_evev(int val);
int is_fill(int maze[H][W]);
void set_start_goal(int maze[H][W]);

void solve_maze(int maze[H][W]);


----------aa.c----------------------------------------------------

#include "a.h"
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main(void)
{
int maze[H][W] = {0};

srand((unsigned int)time(NULL));

create_maze(maze);

solve_maze(maze);

print_maze(maze);

return 0;
}

void print_maze(int maze[H][W])
{
int i,j;

printf(" ");
for(j=0;j<W;j++)
{
printf("%2d",j%100);
}
printf("\n");

for(i=0;i<H;i++)
{
printf("%2d| ",i%100);
for(j=0;j<W;j++)
{
if(maze[i][j] == WALL)
{
printf("■");
}
else if(maze[i][j] == START)
{
printf("Ｓ");

}
else if(maze[i][j] == GOAL)
{
printf("Ｇ");
}
else if(maze[i][j] == TRACK)
{
printf("・");
}
else
{
printf("　");
}
}
printf(" |%2d\n",i%100);
}
}
void create_maze(int maze[H][W])
{
int i,dir,len,len_max;
int h,w,dx,dy;

for(i=0;i<H;i++)
{
maze[i][0] = maze[i][W-1] = WALL;
}
for(i=0;i<W;i++)
{
maze[0][i] = maze[H-1][i] = WALL;
}
while(is_fill(maze) != TRUE)
{
do
{
do
{
h = to_even(rand()%H);
w = to_even(rand()%W);
}
while(maze[h][w] != WALL);

dir = rand()%4;
dy = (dir-1)%2;
dx = (dir-2)%2;
h += dy;
w += dx;
}
while((0>h||h>=H)||(0>w||w>=W)||maze[h][w]==WALL);

len_max = ((dir%2==0) ? H : W) -3;
len = to_even(rand()%len_max) +2;

i = 0;
while(i++<len && maze[h+dy][w+dx]!=WALL)
{
maze[h][w] = WALL;

h += dy;
w += dx;

system("crear");
print_maze(maze);
usleep(5*10000);
}
}
set_start_goal(maze);
}

void set_start_goal(int maze[H][W])
{
int is_start;

is_start = rand()%2;

if((rand()%2) == 0)
{
maze[0] [(rand()%(W-2)) / 2 * 2 + 1] = (is_start==1)?START:GOAL;
maze[H-1] [(rand()%(W-2)) / 2 * 2 + 1] = (is_start!=1)?START:GOAL;
}
else
{
maze[(rand()%(H-2)) / 2 * 2 + 1][0] = (is_start==1)?START:GOAL;
maze[(rand()%(H-2)) / 2 * 2 + 1][W-1]= (is_start!=1)?START:GOAL;
}
}
int is_fill(int maze[H][W])
{
int i,j;
int is_fill = TRUE;

for(i=2;i<H-2 && is_fill;i+=2)
{
for(j=2; j<W-2 && is_fill;j+=2)
{
if(maze[i][j] == PASS)
{
is_fill = FALSE;
}
}
}

return is_fill;
}
int to_even(int val)
{
return val / 2 *2;
}



-------a.c--------------------------
#include "a.h"
#include<stdio.h>

struct player
{
int y;
int x;
int dir;
};

void solve_maze(int maze[H][W])
{
int x,y;
struct player p;

for(y=0;y<H;y++)
{
for(x=0;x<W;x++)
{
if(maze[y][x] == START)
{
p.x = x;
p.y = y;
}
}
}
⇒
}

No.3 回答者： siffon9 回答日時： 2016/02/12 11:55

> 見ていただけますか？

以前のご質問から思っていたのですが、もう少しやる気を感じさせるコメントができないのでしょうか？
学校の課題か何かわかりませんが、ご自身で解決しないと身につきませんよ。


> 一様プログラムはかけたのですが、コアダンプや無限ループが出てしまいます。

コアダンプは、たぶんメモリアクセスに問題あり。配列変数などで宣言した値を超える番号の要素にアクセスしていないかを確認する。
無限ループは、ループを抜ける条件を満たさない為、その条件が正しいかを確認する。

いずれも、プログラムの要所要所で、その時の関係する変数（配列の要素番号、ループ脱出条件で使用しているもの等）をprintfで表示させて、想定の値を示しているかを確認する。

また、それ以前にそもそもプログラムの考え方が正しいか検証する。
そして、考え方が正しくコードに落ちているかを確認する。

No.2 回答者： siffon9 回答日時： 2016/02/10 20:08

> 一様プログラムはかけたのですが、コアダンプや無限ループが出てしまいます。

バグをみつけて修正しましょう。

この回答へのお礼

見ていただけますか？

お礼日時：2016/02/10 20:51

No.1 回答者： siffon9 回答日時： 2016/02/10 07:15

一番単純なのは、右手（左手）法ですね。

右手を壁にあてながら壁伝いに進んでく方法です。

1. 現地点の進行方向が道で、かつ、現地点の右手方向が壁（スタート地点はこの条件を満たすはず）ならば、一つ前へ進む。
2. 現地点の右手方向が道ならば、右を向き、一つ前へ進む。
3. 現地点の右手方向が壁で、かつ、進行歩行が壁ならば、左を向く

これをひたすら繰り返す。

進行方向差分を、dir[3][] = {{0,1},{1,0},{0,-1},{-1,0}} (右、上、左、下の意味))とし、
現地点の座標を(h,w)とすると

進行方向座標は、(h+dir[i][0], w+dir[i][1]) （iは0～3、　4方向のいずれかを示す。）
進行方向左側座標は、(h+dir[(i+1)%4][0], w+dir[(i+1)%4][1])
進行方向右側座標は、(h+dir[(i+3)%4][0], w+dir[(i+3)%4][1])



もう少し効率的に行う場合は
・分岐点毎に、座標と探索済みの分岐方向をスタックに積む。
・現在の進行方向が行き止まりになったらスタックに積んだ情報を読みだして探索していない方向に進む様にする。

スタックは、配列変数とどこまで積んでいるかを示すインデックス変数で実現可能です。
「座標と探索済み」の情報スタックは、構造体の配列にしてもいいし、各々別の配列変数にしても可です。


スタックとは
https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%BF …

この回答へのお礼

一様プログラムはかけたのですが、コアダンプや無限ループが出てしまいます。

お礼日時：2016/02/10 15:19