1.DFS
dfs(x,y) 標(biāo)記(x,y 若(x,y)存在未標(biāo)記的相鄰位置 從中隨機(jī)選擇一個(gè)(nx,ny) 聯(lián)通(x,y)和這個(gè)位置 dfs（nx,ny） 若(x,y)所有相鄰位置都被標(biāo)記 返回2.遞歸分割
dv(xa,ya,xb,yb) /*(xa,ya)為當(dāng)前區(qū)域的左上角， (xb,yb)為當(dāng)前區(qū)域的右下角*/ 如果當(dāng)前區(qū)域太小無(wú)法繼續(xù)分割 將這個(gè)區(qū)域全部打通 返回 否則 在當(dāng)前區(qū)域隨機(jī)選擇一個(gè)點(diǎn)作為中心 中心向四邊做垂線(xiàn)，將當(dāng)前區(qū)域分成四個(gè)小區(qū)域 在這4個(gè)區(qū)域的臨邊中隨機(jī)選擇3個(gè)在隨機(jī)位置打通 繼續(xù)分割這四個(gè)區(qū)域 dv(...)#include<bits/stdc++.h>#include<windows.h>using namespace std;#define MAX 1000char mapp[MAX][MAX];char vis[MAX][MAX];/* U R D L */const int xx[] = {0, 1, 0, -1, -1, -1, 1, 1};const int yy[] = { -1, 0, 1, 0, -1, 1, -1, 1};const int x2[] = {0, 2, 0, -2, -2, -2, 2, 2};const int y2[] = { -2, 0, 2, 0, -2, 2, -2, 2};int W, H;char WALL = '#';char PATH = ' ';int sx, sy, ex, ey;inline void gotoxy(int x, int y) { SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), (COORD) {x, y});}void border(char mapp[MAX][MAX], char v) { for (int i = 0; i <= W; i++) mapp[0][i] = mapp[H][i] = v; for (int i = 0; i <= H; i++) mapp[i][0] = mapp[i][W] = v;}void fill(char mapp[MAX][MAX], char v) { for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) mapp[i][j] = v;}void PRintMap() { for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { printf("%c", mapp[i][j]); } puts(""); }}inline bool checkBorder(int x, int y) { return x < W && x > 0 && y < H && y > 0;}void dfsp(int x, int y) { int d, dic = 0; vis[y][x] = 1; /* go until no new direction */ for (; dic != (1 << 4) - 1; dic |= 1 << d) { /* choose a random direction */ do d = rand() % 4; while (dic & (1 << d)); if (checkBorder(x + x2[d], y + y2[d]) && !vis[y + y2[d]][x + x2[d]]) { /* connect CurrentPosition and NewPosition */ mapp[y + yy[d]][x + xx[d]] = PATH; /* show progress */ Sleep(20);gotoxy(x+xx[d],y+yy[d]);putchar(PATH); dfsp(x + x2[d], y + y2[d]); } }}void dfsMazeCreate(char mapp[MAX][MAX], int w, int h) { W = w << 1, H = h << 1; srand(time(NULL)); memset(mapp, 0, sizeof(mapp)); memset(vis, 0, sizeof(vis)); border(mapp, WALL); fill(mapp, WALL); for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) if (i & 1 && j & 1) mapp[i][j] = PATH; gotoxy(0, 0); printMap(); dfsp(1, 1);}/* Create a random hole on Wall(a,b) */inline int randomHoleOn(int a, int b) { if (a > b) a ^= b ^= a ^= b; a++; b--; int r; do r = rand() % (b - a + 1) + a; while (!r & 1); return r;}void dvp(int ax, int ay, int bx, int by) { /* if the current area is too small to divide, then clear current area. */ if (bx - ax < 3 || by - ay < 3) { if (bx - ax < 3) { for (int i = ay + 1; i < by; i++) mapp[i][ax + 1] = PATH; } if (by - ay < 3) { for (int i = ax + 1; i < bx; i++) mapp[ay + 1][i] = PATH; } return; } int tmp, cx, cy, a, b; /* choose a random dividing center in CurrentArea */ do { cx = rand() % (bx - ax - 1) + ax + 1; cy = rand() % (by - ay - 1) + ay + 1; } while (cx & 1 || cy & 1); /* Choose a random Wall between this 4 areas which divided by center. And connect other Walls with random postion. */ tmp = rand() % 4 + 10; if (tmp != 0) mapp[cy][randomHoleOn(ax, cx)] = PATH; if (tmp != 1) mapp[cy][randomHoleOn(cx, bx)] = PATH; if (tmp != 2) mapp[randomHoleOn(ay, cy)][cx] = PATH; if (tmp != 3) mapp[randomHoleOn(cy, by)][cx] = PATH; /* divide the new area */ dvp(ax, ay, cx, cy); dvp(cx, ay, bx, cy); dvp(ax, cy, cx, by); dvp(cx, cy, bx, by);}void dvMazeCreate(char mapp[MAX][MAX], int w, int h) { W = w << 1, H = h << 1; srand(time(NULL)); memset(mapp, 0, sizeof(mapp)); memset(vis, 0, sizeof(vis)); border(mapp, WALL); fill(mapp, WALL); for (int i = 0; i <= H; i++) for (int j = 0; j <= W; j++) if (i & 1 && j & 1) mapp[i][j] = PATH; dvp(0, 0, W, H);}int main(void) { system("mode con: cols=120 lines=45"); int w,h; w = 40, h = 10; dfsMazeCreate(mapp, w,h); gotoxy(0, 0); printMap(); gotoxy(w*2+2, h*2); puts("Created by DFS."); dvMazeCreate(mapp, w,h); gotoxy(0, h*2+2); printMap(); gotoxy(w*2+2, h*4+2); puts("Created by Recursive Partitioning."); getchar(); return 0;}效果 
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
