原文：http://tieba.baidu.com/p/2596809144
#include<iostream.h> #include"time.h" #include"stdlib.h" const char road = ' '; const char wall = 'w'; const char connect = 1; const char began = 26; const char end = 26; const char path = '.'; const char up = 24; const char down = 25; const char right = 26; const char left = 27; const char walked =wall; void Outmaze(int size,char **block); void Modify(int size,char ** block); void Join(int size,char ** block); char ** InitializeMaze(int size) {//this function used to create a random maze //create a 2D array to store the maze char **block=new char*[size] ; for(int n=0;n<size;n++) { block[n]=new char[size]; } //initialize the 2D array for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { if(i%2==0&&j%2==0) { block[i][j]=road; } if(i%2!=0&&j%2!=0) { block[i][j]=wall; } else { if(i%2!=0||j%2!=0) { if(rand()%2<1) { block[i][j]=road; } else { block[i][j]=wall; } } } } } //but the 2D array is not a maze , we should modify it Modify(size,block); return block; } void Outmaze(int size,char **block) {//output the maze //output the top bound for(int m=0;m<size*2+3;m++) cout<<connect; cout<<endl; for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { if(j==0) {//output the left bound cout<<connect<<' '; } cout<<block[i][j]<<' '; if(j==size-1) {//output the right bound cout<<connect; } } cout<<endl; } //output the bottom bound for(int n=0;n<size*2+3;n++) cout<<connect; cout<<endl; } bool TestConnect(int size,int x,int y,char ** block) {//test wether exists the problem of close int n=0; if((x-1<0)||(block[x-1][y]==connect)){n++;} if((x+1>size-1)||(block[x+1][y]==connect)){n++;} if((y-1<0)||(block[x][y-1]==connect)){n++;} if((y+1>size-1)||(block[x][y+1]==connect)){n++;} if(n>=2) { return true; } else { return false; } } int TagConnect(int size,int x,int y,char ** block) {//tag the walls that connected to the bound as "connect" //tag the walls and solve problem of close if((block[x][y]==wall)&&(!TestConnect(size,x,y,block))) {//if the block is wall and is not close then tag it as "connect" block[x][y]=connect; } else {//if the block cause close then tag it as "road" block[x][y]=road; return 0; } //go along four directs to continue this work if((x-1>=0)&&block[x-1][y]==wall) TagConnect(size,x-1,y,block);//go up if((x+1<=size-1)&&block[x+1][y]==wall) TagConnect(size,x+1,y,block);//go down if((y-1>=0)&&block[x][y-1]==wall) TagConnect(size,x,y-1,block);//go left if((y+1<=size-1)&&block[x][y+1]==wall) TagConnect(size,x,y+1,block);//go right return 0; } void Modify(int size,char ** block) {//modify the array to be a maze //tag the walls that connected to the bound for(int i=1;i<size-1;i=i+2) { TagConnect(size,i,size-1,block);//from the right bound TagConnect(size,i,0,block);//from the left bound TagConnect(size,size-1,i,block);//from the bottom bound TagConnect(size,0,i,block);//from the top bound } //there still some walls which are isolation (not connect to any bounds),we have to solve the problem Join(size,block); } void Join(int size,char ** block) {//connect the walls that are isolation to the bound for(int i=0;i<size-1;i++) { for(int j=0;j<size-1;j++) { if(block[i][j]==road&&!(i%2==0&&j%2==0)&&!(i%2!=0&&j%2!=0)) { if(!TestConnect(size,i,j,block)) { block[i][j]=wall; TagConnect(size,i,j,block); } } } } } bool FindPath(int size,int x,int y ,int o,int p,char ** block) {//find the path of the maze. x,y are the coordinate of the began point // and o,p are the coordinate of the end point if((x==o)&&(y==p)) { block[x][y]=3; return true; } block[x][y]=walked; if((x-1>=0)&&block[x-1][y]==road) { if(FindPath(size,x-1,y,o,p,block)) { block[x][y]=up; return true; } } if((x+1<=size-1)&&block[x+1][y]==road) { if(FindPath(size,x+1,y,o,p,block)) { block[x][y]=down; return true; } } if((y-1>=0)&&block[x][y-1]==road) { if(FindPath(size,x,y-1,o,p,block)) { block[x][y]=left; return true; } } if((y+1<=size-1)&&block[x][y+1]==road) { if(FindPath(size,x,y+1,o,p,block)) { block[x][y]=right; return true; } } block[x][y]=road; return false; } main() { do { cout<<"welcome !"<<endl; srand((unsigned int) time(0)); cout<<"please input the size of the maze:"<<endl; int size; cin>>size; size=size/2*2+1; char ** block=InitializeMaze(size); block[0][0]=began; block[size-1][size-1]=end; Outmaze(size,block); cout<<"press any key to show answer!"<<endl; char n; cin>>n; block[size-1][size-1]=road; FindPath(size,0,0,size-1,size-1,block); Outmaze(size,block); }while(true); return 0; }
路径：
