#include<iostream.h>

#include"time.h"

#include"stdlib.h"

const char road = ' ';

const char wall = 'w';

const char connect = ;

const char began = ;

const char end = ;

const char path = '.';

const char up = ;

const char down = ;

const char right = ;

const char left = ;

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=;n<size;n++)

{

block[n]=new char[size];

}

//initialize the 2D array

for(int i=;i<size;i++)

{

for(int j=;j<size;j++)

{

if(i%==&&j%==)

{

block[i][j]=road;

}

if(i%!=&&j%!=)

{

block[i][j]=wall;

}

else

{

if(i%!=||j%!=)

{

if(rand()%<)

{

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=;m<size*+;m++)

cout<<connect;

cout<<endl;

for(int i=;i<size;i++)

{

for(int j=;j<size;j++)

{

if(j==)

{//output the left bound

cout<<connect<<' ';

}

cout<<block[i][j]<<' ';

if(j==size-)

{//output the right bound

cout<<connect;

}

}

cout<<endl;

}

//output the bottom bound

for(int n=;n<size*+;n++)

cout<<connect;

cout<<endl;

}

bool TestConnect(int size,int x,int y,char ** block)

{//test wether exists the problem of close

int n=;

if((x-<)||(block[x-][y]==connect)){n++;}

if((x+>size-)||(block[x+][y]==connect)){n++;}

if((y-<)||(block[x][y-]==connect)){n++;}

if((y+>size-)||(block[x][y+]==connect)){n++;}

if(n>=)

{

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 ;

}

//go along four directs to continue this work

if((x->=)&&block[x-][y]==wall)

TagConnect(size,x-,y,block);//go up

if((x+<=size-)&&block[x+][y]==wall)

TagConnect(size,x+,y,block);//go down

if((y->=)&&block[x][y-]==wall)

TagConnect(size,x,y-,block);//go left

if((y+<=size-)&&block[x][y+]==wall)

TagConnect(size,x,y+,block);//go right

return ;

}

void Modify(int size,char ** block)

{//modify the array to be a maze 

//tag the walls that connected to the bound

for(int i=;i<size-;i=i+)

{

TagConnect(size,i,size-,block);//from the right bound

TagConnect(size,i,,block);//from the left bound

TagConnect(size,size-,i,block);//from the bottom bound

TagConnect(size,,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=;i<size-;i++)

{

for(int j=;j<size-;j++)

{

if(block[i][j]==road&&!(i%==&&j%==)&&!(i%!=&&j%!=))

{

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]=;

return true;

}

block[x][y]=walked;

if((x->=)&&block[x-][y]==road)

{

if(FindPath(size,x-,y,o,p,block))

{

block[x][y]=up;

return true;

}

}

if((x+<=size-)&&block[x+][y]==road)

{

if(FindPath(size,x+,y,o,p,block))

{

block[x][y]=down;

return true;

}

}

if((y->=)&&block[x][y-]==road)

{

if(FindPath(size,x,y-,o,p,block))

{

block[x][y]=left;

return true;

}

}

if((y+<=size-)&&block[x][y+]==road)

{

if(FindPath(size,x,y+,o,p,block))

{

block[x][y]=right;

return true;

}

}

block[x][y]=road; 

return false;

}

main()

{

do

{

cout<<"welcome !"<<endl;

srand((unsigned int) time());

cout<<"please input the size of the maze:"<<endl;

int size;

cin>>size;

size=size/*+;

char ** block=InitializeMaze(size);

block[][]=began;

block[size-][size-]=end;

Outmaze(size,block);

cout<<"press any key to show answer!"<<endl;

char n;

cin>>n;

block[size-][size-]=road;

FindPath(size,,,size-,size-,block);

Outmaze(size,block);

}while(true);

return ;

}