迷路
迷路
迷路の説き方について考えているのですが、お力お貸しください。
{
{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が通れるとこだと思ってください。
プログラムで出口までいけるようにするにはどうしたらいいでしょうか?
{
{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が通れるとこだと思ってください。
プログラムで出口までいけるようにするにはどうしたらいいでしょうか?
Re:迷路
こういう迷路ですね。
とりあえず①がスタートだとしますね。
こういうの再起関数うまくつかえば解ける気がしますね。
でも、再起で解く方法ぱっと思いつきません・・。
私が考え付く範囲でしたら、
自分のいる地点から過去に通った方向を除く進行方向に対して3方向を左から順に調べ、いけるほうにすすみます。
自分が現在むいている方向を変数に保存します。
いつも左から調べれば無限ループになることもないでしょう。
しかし、どうも再起関数の方がいいきがします。
ちょっと考えさせてください。
すみません。
■①■■■■■■■■■■■■■■ ■ ■■■■■■■■■ ■ ■■■■ ■■ ■ ■■■■ ■■■■■■ ■■ ■ ■■■■ ■■■■■■ ■■ ■ ■■ ■■ ■ ■ ■■ ■■■■ ■■■■■■ ■■■■ ■■■■ ■ ■■■■ ■■■■■■■■■ ■ ■■■■■■■■■■■■■■②■まず、図のように番号をつけましたが、どちらがゴールですか?
とりあえず①がスタートだとしますね。
こういうの再起関数うまくつかえば解ける気がしますね。
でも、再起で解く方法ぱっと思いつきません・・。
私が考え付く範囲でしたら、
自分のいる地点から過去に通った方向を除く進行方向に対して3方向を左から順に調べ、いけるほうにすすみます。
自分が現在むいている方向を変数に保存します。
いつも左から調べれば無限ループになることもないでしょう。
しかし、どうも再起関数の方がいいきがします。
ちょっと考えさせてください。
すみません。
Re:迷路
すみません、間違いが多かったので、先ほどの投稿消しました。
プログラム修正しました。
しかし、、すごく無駄な処理をしています・・。
必ずもっとスマートにかけると思います。。。
angleという向きを設定して、今の進行方向に対して
・左 進行方向 右
の順番にいけるかどうか調査し、いけなかったら戻ります。
いけるかどうかはその配列要素が0か1かで判断します。
常に進行方向に対して左から調査しているので、
同じいきどまりでうろうろすることはありません。
とうとう再起関数では書きませんでした。
一応できたので、これでいいか見てください。
ans関数の中はどうにもなりません・・。
これ以上スマートに書く方法自分では思いつきません。
ごめんなさい。
とりあえず修正版アップします。
迷路はもっと複雑にしました。
始点はi,jの宣言に代入してください。
終点の設定はいりません。一番下に来れば自動的に終了します。
これでやりたいことがあってるか確認してください。
汚いソースですみません・・・。
プログラム修正しました。
しかし、、すごく無駄な処理をしています・・。
必ずもっとスマートにかけると思います。。。
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;
}
Re:迷路
#include <stdio.h> #include <string.h> void Print(int maze[/url][16]) { char *mark[/url] = {"■", " ", "x", }; 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; }
Re:迷路
お久しぶりです。
通りすがりさんのやり方は面白いですね。
行き止まりから0が伝播して、最終的に道筋だけが残るんですね。
ただ行き止まりがループしていると、その部分も出力されてしまいますね。
例えば下のようなのです。
通りすがりさんのやり方は面白いですね。
行き止まりから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にしてください。
Re:迷路
お目汚しのコードです。
再帰関数を作ってみました。
先へ進めなくなったら前の分岐まで戻って別の道を探す、
という手順を出力しています。
再帰関数を作ってみました。
先へ進めなくなったら前の分岐まで戻って別の道を探す、
という手順を出力しています。
#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; }