#include<iostream>
#include"AQueue.h"
#include<iomanip>
using namespace std;
#define MAZESIZE 8
typedef struct _Position
{
int x;
int y;
}Position;
Position Dim[4] = {{1 , 0},
{0 , 1},
{0 ,-1},
{-1, 0}};
Position parentTable[8][8];
char maze[8][8] = {
{ '#','#', '#' ,'#' ,'#', '#', '#' ,'#' },
{ '.','.', '.' ,'#' ,'.', '#', '.' ,'.' },
{ '#','#', '.' ,'#' ,'.', '#', '.' ,'#' },
{ '#','.', '.' ,'.' ,'.', '.', '.' ,'#' },
{ '#','.', '#' ,'#' ,'.', '#', '.' ,'#' },
{ '#','.', '.' ,'.' ,'.', '#', '.' ,'#' },
{ '#','#', '.' ,'.' ,'.', '.', '.' ,'#' },
{ '#','#', '#' ,'#' ,'#', '#', '#' ,'#' },
};
void PrintMaze();
void initParent();
int main()
{
initParent();
AQueue<Position> pathQue(1);
Position start = {1,0};
Position finalPos = {1,7};
pathQue.enqueue(start);
while(pathQue.length() != 0)
{
Position nowPos = pathQue.dequeue();
maze[nowPos.x][nowPos.y] = '0';
for(int dim = 0 ; dim < 4 ;dim++)
{
Position nextPos;
nextPos.x = nowPos.x + Dim[dim].x;
nextPos.y = nowPos.y + Dim[dim].y;
if ((nextPos.x >= 0) && (nextPos.x <= 7) && (nextPos.y >= 0) && (nextPos.y <= 7) && maze[nextPos.x][nextPos.y] != '#' && maze[nextPos.x][nextPos.y] != '0')
{
parentTable[nextPos.x][ nextPos.y] = nowPos;
pathQue.enqueue(nextPos);
maze[nextPos.x][nextPos.y] = '0';
if(nextPos.x == finalPos.x && nextPos.y == finalPos.y)
{
goto sol_start;
}
}
}
PrintMaze();
}
sol_start:
if(pathQue.length() == 0)
{
cout<<"the maze has no solution"<<endl;
return 0;
}
Position currPos = finalPos;
cout<<"Start solving......"<<endl;
int step = 0;
while((currPos.x != start.x) || (currPos.y != start.y))
{
maze[currPos.x][currPos.y] = 'x';
Position tempPos;
tempPos.x = parentTable[currPos.x][currPos.y].x;
tempPos.y = parentTable[currPos.x][currPos.y].y;
currPos = tempPos;
step++;
}
maze[currPos.x][currPos.y] = 'x';
PrintMaze();
cout<<"Total step: "<<step<<endl;
return 0;
}
void PrintMaze()
{
static int num = 1;
cout<<"-------------------"<<endl;
for(int i = 0 ;i < 8 ; i++)
{
for(int j = 0 ; j < 8 ; j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
cout<<"-------------------"<<endl;
num++;
}
void initParent()
{
for(int i = 0 ; i < 8 ; i++)
{
for(int j = 0 ; j < 8 ; j++)
{
parentTable[i][j].x = -1;
parentTable[i][j].y = -1;
}
}
}
執行結果：
-------------------
# # # # # # # #
0 0 . # . # . .
# # . # . # . #
# . . . . . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # . # . # . #
# . . . . . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # . # . #
# . . . . . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # . # . #
# . 0 . . . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # . # . #
# 0 0 0 . . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # . # . #
# 0 0 0 0 . . #
# . # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # . # . #
# 0 0 0 0 . . #
# 0 # # . # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # 0 # . #
# 0 0 0 0 0 . #
# 0 # # 0 # . #
# . . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # 0 # . #
# 0 0 0 0 0 . #
# 0 # # 0 # . #
# 0 . . . # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # 0 # . #
# 0 0 0 0 0 . #
# 0 # # 0 # . #
# 0 . . 0 # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # . # . .
# # 0 # 0 # . #
# 0 0 0 0 0 0 #
# 0 # # 0 # . #
# 0 . . 0 # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # . #
# 0 0 0 0 0 0 #
# 0 # # 0 # . #
# 0 . . 0 # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # . #
# 0 0 0 0 0 0 #
# 0 # # 0 # . #
# 0 0 . 0 # . #
# # . . . . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # . #
# 0 0 0 0 0 0 #
# 0 # # 0 # . #
# 0 0 0 0 # . #
# # . . 0 . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # . #
# # . . 0 . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # . #
# # . . 0 . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # . #
# # 0 . 0 . . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # . #
# # 0 0 0 0 . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # . #
# # 0 0 0 0 . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # . .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # 0 .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # 0 .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 . #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # 0 .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 0 #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # 0 .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 0 #
# # # # # # # #
-------------------
-------------------
# # # # # # # #
0 0 0 # 0 # 0 .
# # 0 # 0 # 0 #
# 0 0 0 0 0 0 #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 0 #
# # # # # # # #
-------------------
Start solving......
-------------------
# # # # # # # #
x x x # 0 # x x
# # x # 0 # x #
# 0 x x x x x #
# 0 # # 0 # 0 #
# 0 0 0 0 # 0 #
# # 0 0 0 0 0 #
# # # # # # # #
-------------------
Total step: 11
留言列表
