wikipedia Maze solving algorithm - Wikipedia
迷路作成です。
書いてみました。
#include<iostream> #include<string> #include<cstdio> #include<ctime> #include<algorithm> #define x 100 //横 #define y 50//縦 int MAP[x+1][y+1]; //table int site(0); //サイトの登録数 int xx[x*y/4],yy[x*y/4]; //サイト座標 int dx[]={2,0,-2,0}; //方向関連 int dy[]={0,2,0,-2}; int dirtable[24][4] = { 0,1,2,3, 0,1,3,2, 0,2,1,3, 0,2,3,1, 0,3,1,2, 0,3,2,1, 1,0,2,3, 1,0,3,2, 1,2,0,3, 1,2,3,0, 1,3,0,2, 1,3,2,0, 2,0,1,3, 2,0,3,1, 2,1,0,3, 2,1,3,0, 2,3,0,1, 2,3,1,0, 3,0,1,2, 3,0,2,1, 3,1,0,2, 3,1,2,0, 3,2,0,1, 3,2,1,0 }; void site_add(int a , int b){ xx[site] = a; yy[site] = b; site++; } //サイトの選択とサイトの残量 bool select(int* a, int* b){ if(site == 0) return false; site--; int c = (int)(site*(rand()/(RAND_MAX+1.0))); *a = xx[c]; *b = yy[c]; xx[c] = xx[site]; yy[c] = yy[site]; return true; } int main(void){ int d,e; int* t; srand((unsigned)time(NULL)); //時間での乱数初期化 std::fill(MAP[0],MAP[0]+(x+1)*(y+1),1); //tableをtrueで初期化 for(int i=3;i<=x-3;i++){ for(int j=3;j<=y-3;j++){ MAP[i][j] = 0; } } MAP[2][3] = MAP[x-2][y-3] = 0; for (int i = 4; i<= y-4; i+=2) { site_add(2, i); site_add(x-2, i); } for(int i=4;i<= x-4;i+=2){ site_add(i,2); site_add(i,y-2); } while (select(&d, &e)){ //selectでfalseになるまで回す int f,x_1,y_1; for (;;) { t = dirtable[(int)(24 * (rand() / (RAND_MAX + 1.0)))]; for(f=3;f >= 0;f--){ int h = t[f]; x_1 = d + dx[h]; y_1 = e + dy[h]; if (MAP[x_1][y_1] == 0) break; } if(f < 0) break; MAP[(d+x_1)/2][(e+y_1)/2] = 1; d = x_1; e = y_1; MAP[d][e] = 1; site_add(d, e); } } for (int i = 2; i<=y-2; i++) { for (int j = 2;j<=x-2; j++){ if (MAP[j][i]) std::cout << "|"; //true else std::cout << " "; //false } std::cout << std::endl; } return 0; }