#include "maze.h"
Maze::Maze(QObject *parent) : QObject(parent)
{
}
void Maze::set_n(int tn)
{
n = tn;
nn = n/2;
}
int Maze::get_n()
{
return n;
}
void Maze::printPath()
{
bfs();
for(int i = len_path-1; i >= 0; i--) {
if(maze[path[i].x][path[i].y]==0) {
maze[path[i].x][path[i].y] = 6;
}
}
}
void Maze::recoverPath()
{
for(int i = len_path-1; i >= 0; i--) {
if(maze[path[i].x][path[i].y]==6) {
maze[path[i].x][path[i].y] = 0;
}
}
}
void Maze::mazeInit()
{
for(int i=0; i<=nn*2+2; ++i)
for(int j=0; j<=nn*2+2; ++j)
maze[i][j] = 1;
for(int i=0, j=2*nn+2; i<=2*nn+2; ++i)
{
maze[i][0] = 0;
maze[i][j] = 0;
}
for(int i=0, j=2*nn+2; i<=2*nn+2; ++i)
{
maze[0][i] = 0;
maze[j][i] = 0;
}
maze[2][1] = 2;
maze[2*nn][2*nn+1] = 3;
srand((unsigned)time(NULL));
searchPath(rand()%nn+1, rand()%nn+1);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
maze[i][j] = maze[i+1][j+1];
}
}
len_path = 0;
}
int Maze::searchPath(int x, int y)
{
static int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int zx = x*2;
int zy = y*2;
int next, turn, i;
maze[zx][zy] = 0;
turn = rand()%2 ? 1 : 3;
for(i=0, next=rand()%4; i<4; ++i, next=(next+turn)%4)
if(maze[zx+2*dir[next][0]][zy+2*dir[next][1]] == 1)
{
maze[zx+dir[next][0]][zy+dir[next][1]] = 0;
searchPath(x+dir[next][0], y+dir[next][1]);
}
return 0;
}
void Maze::print()
{
bfs();
}
void Maze::bfs()
{
int front, tail, sx, sy;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(maze[i][j] == 2)
{
sx = i; sy = j;
}
front = tail = 0;
q[tail].x = sx;
q[tail].y = sy;
q[tail].pre = -1;
tail++;
int x, y, nx, ny;
bool fg = false;
while(front < tail)
{
x = q[front].x;
y = q[front].y;
for(int i = 0; i < 4; i++)
{
nx = x+dx[i];
ny = y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&maze[nx][ny]==0)
{
maze[nx][ny] = 5;
q[tail].x = nx;
q[tail].y = ny;
q[tail].pre = front;
tail++;
}
if(maze[nx][ny] == 3){
q[tail].x = nx;
q[tail].y = ny;
q[tail].pre = front;
tail++;
fg = true;
len_path = 0;
path[len_path].x = nx;
path[len_path].y = ny;
len_path++;
getPath(front);
}
}
if(fg)break;
front++;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(maze[i][j] == 5)
maze[i][j] = 0;
}
void Maze::getPath(int pos)
{
while(pos != -1)
{
path[len_path].x = q[pos].x;
path[len_path].y = q[pos].y;
len_path++;
pos = q[pos].pre;
}
}
