PowerPoint Presentation
Maze Problem
Find a path from the maze entry to maze exit.
To represent a maze, we set the following array mg in which each element represents a block. 0 indicates the block is a path, and 1 indicates the block is a wall.
int mg[M+1][N+1]={ /*M=10,N=10*/
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
As shown in the figure, each path block has four neighboring blocks. For a given block (i,j), we name the directions of its neighboring blocks in the clockwise manner. When explore the maze path, we need to check all the four possible directions. In such process, the block should be pushed into a stack. The stack and block are defined as follows:
typedef struct stack_type{
block_type block[Max]; /*blocks are stack elements*/
int top; /*stack top*/
} stack_type; /*stack definition*/
stack_type Stack;
Stack.top = -1; /*stack initialization*/
As shown in the figure, each path block has four neighboring blocks. For a given block (i,j), we name the directions of its neighboring blocks in the clockwise manner. When explore the maze path, we need to check all the four possible directions. In such process, the block should be pushed into a stack. The stack and block are defined as follows:
typedef struct stack_type{
block_type block[Max]; /*blocks are stack elements*/
int top; /*stack top*/
} stack_type; /*stack definition*/
typedef struct block_type{
int i, j; /* row & column number */
int di; /*next exploring direction*/
}block_type; /*block definition*/
Maze Problem
Find a path from the maze entry to maze exit.