/*
* 迷路を解く
* 関数solve_mazeに必要な処理を記述する
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* 迷路のサイズ */
#define W 31
#define H 37
/* 迷路のマーク */
#define PASS 0
#define WALL 1
#define START 2
#define GORL 4
#define TRACK 8
#define TRUE 1
#define FALSE 0
void print_maze(int maze[H][W]);
void create_maze(int maze[H][W]);
void set_start_gorl(int maze[H][W]);
int is_fill(int maze[H][W]);
void solve_maze(int maze[H][W]);
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;
for(i=0; i<H; i++)
{
for(j=0; j<W; j++)
{
if(maze[i][j] == WALL)
{
printf("壁");
}
else if(maze[i][j] == START)
{
printf("Ｓ");
}
else if(maze[i][j] == GORL)
{
printf("Ｇ");
}
else if(maze[i][j] == TRACK)
{
printf("・");
}
else
{
printf(" ");
}
}
printf("\n");
}
}
/* 作成 */
void create_maze(int maze[H][W])
{
int i, dir, h, w, len, len_max;
/* フィールドを用意し、外周を壁で囲む */
for(i=0; i<H; i++)
{
maze[i][0] = WALL;
maze[i][W-1] = WALL;
}
for(i=0; i<W; i++)
{
maze[0][i] = WALL;
maze[H-1][i] = WALL;
}
/* 壁を伸ばす長さの最大の数(/2)を決定する */
len_max = ((H>W) ? W : H) / 2 - 5;
/* 壁になるべき場所が、全て壁になるまで繰り返す */
while(is_fill(maze) != TRUE)
{
do
{
/* ランダムに壁上の1点を選択する */
do
{
h = rand() % H / 2 * 2;
w = rand() % W / 2 * 2;
}
while(maze[h][w] != WALL);
/* 伸ばす壁の方向を決める */
dir = rand() % 4; /* 0:上, 1:左, 2:下, 3:右 */
h = (dir-1) % 2 + h; /* dir=0:-1, dir=2:1 */
w = (dir-2) % 2 + w; /* dir=1:-1, dir=3:1 */
}
while((0>h||h>=H)||(0>w||w>=W)||maze[h][w]==WALL);
/* 伸ばす長さを決める */
len = rand() % len_max * 2 + 2;
/* 壁を伸ばす */
i = 0;
while(i++<len && maze[(dir-1)%2+h][(dir-2)%2+w]!=WALL)
{
maze[h][w] = WALL;
h = (dir-1) % 2 + h; /* 0:上, 1:左, 2:下, 3:右 */
w = (dir-2) % 2 + w;
}
}
/* スタートとゴールを設定する */
set_start_gorl(maze);
}
/* スタートとゴールを設定する */
void set_start_gorl(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:GORL;
maze[H-1][(rand() % (W-2)) / 2 * 2 + 1] = (is_start!=1)?START:GORL;
}
else
{
/* 左右の場合 */
maze[(rand() % (H-2)) / 2 * 2 + 1][0] = (is_start==1)?START:GORL;
maze[(rand() % (H-2)) / 2 * 2 + 1][W-1] = (is_start!=1)?START:GORL;
}
}
/* 壁になるべき箇所が埋まっているかチェックする(TRUE/FALSE) */
int is_fill(int maze[H][W])
{
int i, j;
/* 偶数番目に壁がないところがあるかチェックする */
for(i=2; i<H-2; i+=2)
{
for(j=2; j<W-2; j+=2)
{
/* 通路の場所がある場合はFALSE */
if(maze[i][j] == PASS)
{
return FALSE;
}
}
}
/* 通路の場所がない場合はTRUE */
return TRUE;
}
void solve_maze(int maze[H][W])
{
/*
スタートとゴールを探し、その間の経路を求める
経路にはTRACKを代入する
*/
int i, j, x, y;
/* スタート位置検索 */
x = y = 0;
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
if( maze[i][j] == START )
{
y = i;
x = j;
}
}
}
rec_track( maze, y, x, maze );
/* 必要な処理を記述してください */
}
int rec_track(int curmaze[H][W], int y, int x, int maze[H][W])
{
/* x, y 現在の座標 */
/* maze -> 元の迷路 */
/* curmaze -> 現在の迷路 */
int i, j;
int flag = FALSE;
do
{
/* newmaze -> 解析する迷路 */
int newmaze[H][W];
/* 迷路をコピー */
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
newmaze[i][j] = curmaze[i][j];
}
}
/* 現在の上(y-1)を解析 */
if( y > 0 )
{
if( newmaze[y-1][x] == GORL )
{
/* ゴールなら経路をコピーする */
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
maze[i][j] = newmaze[i][j];
}
}
/* フラグを立てる */
flag = TRUE;
break;
}
if( newmaze[y-1][x] == PASS )
{
/* 解析位置が通路ならTRACKを代入して再帰で呼び出す */
newmaze[y-1][x] = TRACK;
if( rec_track( newmaze, y-1, x, maze ) != FALSE )
{
/* フラグを立てる */
flag = TRUE;
break;
}
/* 解析結果がGORLに繋がってなければ元に戻す */
newmaze[y-1][x] = PASS;
}
}
/* 現在の右(x+1)を解析 */
if( x < W )
{
if( newmaze[y][x+1] == GORL )
{
/* ゴールなら経路をコピーする */
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
maze[i][j] = newmaze[i][j];
}
}
/* フラグを立てる */
flag = TRUE;
break;
}
if( newmaze[y][x+1] == PASS )
{
/* 解析位置が通路ならTRACKを代入して再帰で呼び出す */
newmaze[y][x+1] = TRACK;
if( rec_track( newmaze, y, x+1, maze ) != FALSE )
{
/* フラグを立てる */
flag = TRUE;
break;
}
/* 解析結果がGORLに繋がってなければ元に戻す */
newmaze[y][x+1] = PASS;
}
}
/* 現在の下(y+1)を解析 */
if( y < H )
{
if( newmaze[y+1][x] == GORL )
{
/* ゴールなら経路をコピーする */
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
maze[i][j] = newmaze[i][j];
}
}
/* フラグを立てる */
flag = TRUE;
break;
}
if( newmaze[y+1][x] == PASS )
{
/* 解析位置が通路ならTRACKを代入して再帰で呼び出す */
newmaze[y+1][x] = TRACK;
if( rec_track( newmaze, y+1, x, maze ) != FALSE )
{
/* フラグを立てる */
flag = TRUE;
break;
}
/* 解析結果がGORLに繋がってなければ元に戻す */
newmaze[y+1][x] = PASS;
}
}
/* 現在の左(x-1)を解析 */
if( x > 0 )
{
if( newmaze[y][x-1] == GORL )
{
/* ゴールなら経路をコピーする */
for(i=0; i<H ; i++)
{
for(j=0; j<W; j++)
{
maze[i][j] = newmaze[i][j];
}
}
/* フラグを立てる */
flag = TRUE;
break;
}
if( newmaze[y][x-1] == PASS )
{
/* 解析位置が通路ならTRACKを代入して再帰で呼び出す */
newmaze[y][x-1] = TRACK;
if( rec_track( newmaze, y, x-1, maze ) != FALSE )
{
/* フラグを立てる */
flag = TRUE;
break;
}
/* 解析結果がGORLに繋がってなければ元に戻す */
newmaze[y][x-1] = PASS;
}
}
break;
}
while( TRUE );
return flag;
}