迷路

[まいこ]

迷路の説き方について考えているのですが、お力お貸しください。

{
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0},
{0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0},
{0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0},
{0,1,0,0,1,1,1,0,0,1,1,1,1,1,1,0},
{0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
};

いまこのように配列に数字がはいっているんです。
0が壁で1が通れるとこだと思ってください。
プログラムで出口までいけるようにするにはどうしたらいいでしょうか？

[管理人]

こういう迷路ですね。

■①■■■■■■■■■■■■■■
■　　　　　　■■■■■■■■■
■　■■■■　　　　　　　　■■
■　■■■■　■■■■■■　■■
■　■■■■　■■■■■■　■■
■　■■　　　■■　　　　　　■
■　■■　■■■■　■■■■■■
■■■■　■■■■　　　　　　■
■■■■　■■■■■■■■■　■
■■■■■■■■■■■■■■②■

まず、図のように番号をつけましたが、どちらがゴールですか？
とりあえず①がスタートだとしますね。

こういうの再起関数うまくつかえば解ける気がしますね。
でも、再起で解く方法ぱっと思いつきません・・。

私が考え付く範囲でしたら、
自分のいる地点から過去に通った方向を除く進行方向に対して３方向を左から順に調べ、いけるほうにすすみます。
自分が現在むいている方向を変数に保存します。

いつも左から調べれば無限ループになることもないでしょう。

しかし、どうも再起関数の方がいいきがします。

ちょっと考えさせてください。
すみません。

[管理人]

すみません、間違いが多かったので、先ほどの投稿消しました。
プログラム修正しました。

しかし、、すごく無駄な処理をしています・・。
必ずもっとスマートにかけると思います。。。

angleという向きを設定して、今の進行方向に対して
・左　進行方向　右
の順番にいけるかどうか調査し、いけなかったら戻ります。
いけるかどうかはその配列要素が0か1かで判断します。

常に進行方向に対して左から調査しているので、
同じいきどまりでうろうろすることはありません。

とうとう再起関数では書きませんでした。

一応できたので、これでいいか見てください。
ans関数の中はどうにもなりません・・。
これ以上スマートに書く方法自分では思いつきません。
ごめんなさい。

とりあえず修正版アップします。
迷路はもっと複雑にしました。

始点はi,jの宣言に代入してください。

終点の設定はいりません。一番下に来れば自動的に終了します。

これでやりたいことがあってるか確認してください。

汚いソースですみません・・・。

#include <stdio.h>
#include <windows.h>
#include <stdlib.h>
#define R1 16
#define R2 16

int ans(int *angle,int **road,int *i,int *j){//angel 1=上　2=右　3=下　4=左

	if(*angle==1){//上向きだったら
		if(road[(*i)][(*j)-1]==1)//左にいけたら
			(*j)-- , *angle=4;//左に進む
		else if(road[(*i)-1][(*j)]==1)//上にいけたら
			(*i)--;//上に進む
		else if(road[(*i)][(*j)+1]==1)//右にいけたら
			(*j)++ , *angle=2;//右に進む
		else{//行き止まりなら
			(*i)++;//来た方向へ戻る
			*angle=3;//方向を変える。
		}
	}
	else if(*angle==2){//右向きだったら
		if(road[(*i)-1][(*j)]==1)//上にいけたら
			(*i)-- , *angle=1;//上に進む
		else if(road[(*i)][(*j)+1]==1)//右にいけたら
			(*j)++;//右に進む
		else if(road[(*i)+1][(*j)]==1)//下にいけたら
			(*i)++ , *angle=3;//下に進む
		else{//行き止まりなら
			(*j)--;
			*angle=4;
		}
	}
	else if(*angle==3){//下向きだったら
		if(road[(*i)][(*j)+1]==1)//右にいけたら
			(*j)++ , *angle=2;//右に進む
		else if(road[(*i)+1][(*j)]==1)//下にいけたら
			(*i)++;//下に進む
		else if(road[(*i)][(*j)-1]==1)//左にいけたら
			(*j)-- , *angle=4;//左に進む
		else{//行き止まりなら
			(*i)--;
			*angle=1;
		}
	}
	else{//左向きだったら
		if(road[(*i)+1][(*j)]==1)//下にいけたら
			(*i)++ , *angle = 3;//下に進む
		else if(road[(*i)][(*j)-1]==1)//左にいけたら
			(*j)--;//左に進む
		else if(road[(*i)-1][(*j)]==1)//上にいけたら
			(*i)-- , *angle = 1;//上に進む
		else{//行き止まりなら
			(*j)++;
			*angle=2;
		}
	}
	if((*i)==R2-1)//一番下まで来たら
		return 0;
	else
		return 1;
}

void disp(int **road,int i,int j){//表示関数
	for(int s=0;s<R1;s++){
		for(int t=0;t<R2;t++){
			if(s==i && t==j)//今いる位置なら
				printf("●");
			else if(road[t]==0)
				printf("■");
			else
				printf("　");
		}
		printf("\n");
	}
	printf("\n\n\n");
	return ;
}

int main(){
	int road[R1][R2]={
		{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
		{0,1,1,1,1,1,1,0,0,1,0,1,0,1,1,0}, 
		{0,1,0,1,0,0,1,1,1,1,1,1,1,1,0,0}, 
		{0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,0}, 
		{0,1,0,1,0,0,1,0,1,0,0,0,0,1,0,0}, 
		{0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0}, 
		{0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0}, 
		{0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0}, 
		{0,1,0,1,1,1,0,1,0,0,0,0,0,0,1,0}, 
		{0,1,1,0,0,0,0,1,0,0,0,0,0,0,1,0},
		{0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0},
		{0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0},
		{0,1,0,0,1,0,1,0,1,1,1,1,1,1,1,0},
		{0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,0},
		{0,0,1,1,1,0,1,0,0,1,1,1,1,1,1,0},
		{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0}
	};

	int *ptr[R2];

	for(int s = 0; s < R2; s++)//別にこんな事しなくてもいいですが、一応2次元配列が**で受け取れるように
		ptr = road;
	
	int **pp = &ptr[0];

	{
		int i=0,j=1,angle=3;
		while(1){
			system("cls");//画面クリア
			if(ans(&angle,pp,&i,&j)==0)
				break;
			disp(pp,i,j);
			Sleep(17*12);//17というのは60fpsの1fあたりの時間
		}

		disp(pp,i,j);

	}
	return 0;
}

[通りすがり]

#include <stdio.h>
#include <string.h>

void Print(int maze[/url][16])
{
    char *mark[/url] = {"■", "  ", "ｘ", };
    int i, j;
    
    for(i = 0; i < 10; i ++){
        for(j = 0; j < 16; j ++){
            printf("%s", mark[maze[j]]);
        }
        putchar('\n');
    }
    return;
}

int Search(int maze[/url][16])
{
    int env, flag = 0, i, j;
    
    for(i = 1; i < 9; i ++){
        for(j = 1; j < 15; j ++){
            if(maze[j] == 1){
                env = maze[i-1][j] + maze[i + 1][j] + maze[j - 1] + maze[j + 1];
                maze[j] = (env > 1);
                flag += (env < 2);
            }
        }
    }
    return flag;
}

void Result(int maze[/url][16])
{
    int temp[10][16];
    int i, j;
    
    memcpy(temp, maze, sizeof(int) * 10 * 16);
    while(Search(temp)) ;
    for(i = 0; i < 10; i ++){
        for(j = 0; j < 16; j ++){
            maze[j] += temp[j];
        }
    }
    return;
}

int main(void)
{
    int maze[/url][16] = {{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,},
                      {0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,},
                      {0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,},
                      {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,},
                      {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,},
                      {0,1,0,0,1,1,1,0,0,1,1,1,1,1,1,0,},
                      {0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,},
                      {0,0,0,0,1,0,0,0,0,1,1,1,1,1,1,0,},
                      {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,},
                      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,},}; 
    
    Print(maze);
    putchar('\n');
    Result(maze);
    Print(maze);
    return 0;
}

[mas]

お久しぶりです。

通りすがりさんのやり方は面白いですね。
行き止まりから0が伝播して、最終的に道筋だけが残るんですね。
ただ行き止まりがループしていると、その部分も出力されてしまいますね。
例えば下のようなのです。

int maze[/url][16] = {{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,},
                      {0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,},
                      {0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,},
                      {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,},
                      {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,},
                      {0,1,0,0,1,1,1,0,0,1,1,1,1,1,1,0,},
                      {0,1,0,0,1,0,1,0,0,1,0,0,0,0,0,0,},
                      {0,0,0,0,1,0,1,0,0,1,1,1,1,1,1,0,},
                      {0,0,0,0,1,1,1,0,0,0,0,0,0,0,1,0,},
                      {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,},};

管理人さんはans関数あたりが苦労されたようなので、簡潔にしてみました。

int ans(int *angle,int **road,int *i,int *j){//angel 0=上　1=右　2=下　3=左
    
    int dx[/url] = {0, 1, 0, -1};
    int dy[/url] = {-1, 0, 1, 0};
    for(int k=0;k<4;k++) {
        if(road[*i+dy[(*angle+3+k)%4]][*j+dx[(*angle+3+k)%4]] == 1) {
            *i += dy[(*angle+3+k)%4], *j += dx[(*angle+3+k)%4], *angle = (*angle+3+k)%4;
            break;
        }
    }
	if((*i)==R2-1)//一番下まで来たら
		return 0;
	else
		return 1;
}

angleを0から始めるようにしたのでmain関数での初期化はangle=2にしてください。

[box]

お目汚しのコードです。
再帰関数を作ってみました。
先へ進めなくなったら前の分岐まで戻って別の道を探す、
という手順を出力しています。

#include <stdio.h>
#include <stdlib.h>

#define X       (16+2)		/* +2は周囲の壁 */
#define Y       (10+2)		/* +2は周囲の壁 */
#define START_X (2)
#define START_Y (1)
#define GOAL_X  (15)
#define GOAL_Y  (10)

void visit(int maze[/url][X], int x, int y);

int main(void)
{
	int maze[Y][X] = {		/* X:水平方向、Y:垂直方向 */
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
		{0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0},
		{0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0},
		{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	};
	
	visit(maze, START_X, START_Y);
	return 0;
}

void visit(int maze[/url][X], int x, int y)
{
	if (maze[y+1][x] == 1 ||
		maze[y-1][x] == 1 ||
		maze[y][x+1] == 1 ||
		maze[y][x-1] == 1)
		printf("(%d,%d)\n", x, y);
	if (x == GOAL_X && y == GOAL_Y) {
		printf("(%d,%d)\n", x, y);
		printf("GOOOOOAL!!\n");
		exit(EXIT_SUCCESS);
	}
	if (maze[y+1][x] == 1)
		maze[y+1][x] = 0, visit(maze, x, y+1), maze[y+1][x] = 1;
	if (maze[y-1][x] == 1)
		maze[y-1][x] = 0, visit(maze, x, y-1), maze[y-1][x] = 1;
	if (maze[y][x+1] == 1)
		maze[y][x+1] = 0, visit(maze, x+1, y), maze[y][x+1] = 1;
	if (maze[y][x-1] == 1)
		maze[y][x-1] = 0, visit(maze, x-1, y), maze[y][x-1] = 1;
}

[管理人]

通りすがりさん、

面白い書き方があるもんですね。参考になります(>_<)
maze[j] = (env > 1);

flag += (env < 2);
このような書き方ができるんですね‥思いつきませんでした(_ _||)


masさん、

なるほど～！そのようにすればよかったんですね。
どうしてもあれ以上先に進めませんでした；　所詮実力もその程度・・・。
なんか実力テストみたいですね＾＾；


boxさん、

なるほど、再起関数はそう書くんですね。

こういう場合は再起関数を使った方がいいんでしょうか？何が一番最適なんでしょう。

[GPGA]

プログラム豆知識として一つだけ。

C言語の比較演算の結果は、それが真ならば非0、偽ならば0が返るのが仕様となっています。
ほとんどの処理系では、真の場合1が返りますが、ある特定の処理系に置いては真の時に-1が返ります。

> maze[j] = (env > 1);
したがって、特定の処理系では、この時にmaze[j]に-1が入る可能性も否定できません。
ただ私は、いままで真に1が入らないコンパイラに出会ったことは一回もありません。

[Justy]

＞ある特定の処理系に置いては真の時に-1が返ります　
　そんな処理系があるとは・・・。

[GPGA]

>そんな処理系があるとは・・・。

以前デジタルトキワ荘のプログラム掲示板でその話が書かれていました。
その時、処理系も書かれていたのですけど、昔トキワ荘の管理人が借りていたサーバ側のミスかなにかで
プログラム板のすべてデータが飛んだことがあり、それと一緒に消えてしまいましたため
残念ながらその記事は現在は存在しません。

[keichan]

>>したがって、特定の処理系では、この時にmaze[j]に-1が入る可能性も否定できません。
確かにそうですね。
FALSEは「0」、TRUEは「非0」と仕様で決められていますからTRUEが1である必要はありません。
#コンパイラベンダが勝手に決めていい

>maze[j] = (env > 1);
>flag += (env < 2);
では処理系依存にならない書き方をすると
maze[j] = (env > 1) ? 1 : 0;
flag += (env < 2) ? 1 : 0;

とかけば問題ないですね。

[Justy]

　今ちょっと調べてみましたが、JIS X3010の規格書によると < > >= <= の各演算子の結果は int型で真の場合は 1を返す(6.5.8)ことが保証されているようです。
　そのコンパイラはＣ言語に準拠していなかったか、昔の古い規格では -1を返してもよかったのか・・・。


＞ 以前デジタルトキワ荘のプログラム掲示板でその話が書かれていました。
　懐かしい名前です（ｗ

[GPGA]

私も規格を確認しようと思い、JISの無料閲覧ページのpdfを選択して30分。
「。。。ただ今、ファイルを開いております。しばらくお待ちください。」が
まだ出ています。orz

[keichan]

あぁ・・・確かにありますね。

|6.5.8 関係演算子
|<(小さい), >(大きい), <=(以下) 及び>=(以上) の各演算子は，指定された関係が真の場合は 1
|を，偽の場合は0を返す。その結果は，型intをもつ。

失礼しました。

[GPGA]

いまだ、pdfは開けずorz
やはり、規格書は持っていたほうがいいですね。
結構な値段が張りますし、特に見ることもないと思っていたので
購入を見合わせていましたが、何かあったとき、正しい事実を確認するために
購入しようと思います。