棧的妙用-實(shí)現(xiàn)迷宮問題

/*used to store the used place*/
int mark[NEW_MAZE_ROWS][NEW_MAZE_COLS];

void mark_init()
{
int i = 0,j = 0;
for(i = 0; i < NEW_MAZE_ROWS ; ++ i)
for(j = 0; j < NEW_MAZE_COLS ; ++ j)
mark[i][j] = 0;
}
intmark_stack_size(int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS])
{
int i = 0,j = 0;

int size = 0;
for(i = 0; i < NEW_MAZE_ROWS; ++ i)
for (j = 0; j < NEW_MAZE_COLS ; ++ j)
{
if(!maze[i][j])
size ++;
}
return size;
}

coordinate nextposition(element a,int dir)
{
coordinate b;
b.col = a.col + move[dir].horiz;
b.row = a.row + move[dir].vert;

return b;
}

int maze_out()
{
element temp;
coordinatenextp;

/*Test the stack is not empty*/
while(top >= 0)
{
/*pop a element*/
temp = *(stack+top);
top --;

/*find on eight directions*/
while(temp.dir < 8)
{
/*get the possible next positions*/
nextp = nextposition(temp,temp.dir);
/*next direction*/
temp.dir ++;

/*success conditions*/
if(nextp.row == EXIT_ROW &&
nextp.col == EXIT_COL)
{
/*save current position*/
stack[++top] = temp;

/*save the exit pointion*/
stack[++top].row = EXIT_ROW;
stack[top].col = EXIT_COL;
stack[top].dir = 0;

/*exit*/
return 1;
}

/*the new position is ok and does not wake*/
if(maze[nextp.row][nextp.col] ==0 &&
mark[nextp.row][nextp.col] == 0)
{
/*mark means that this way has been waked*/
mark[nextp.row][nextp.col] = 1;

/*
*push a element in stack
*save current position and direction
*if this way is failed, used to this position to start new way.
*/
stack[++top] = temp;

/*go to the new position as current position*/
temp.row = nextp.row;
temp.col =nextp.col;
temp.dir = 0;
}
}
}
/*failed*/
return 0;
}

int main()
{
int i = 0;
/*inital the mark array*/
mark_init();
initial_move();

/*create stack*/
stack = (element*)malloc(mark_stack_size(maze)*sizeof(element));
/*if failed*/
if(stack == NULL)
return 0;
/*push a element in stack*/
top ++;
(stack+top)->col = 1;
(stack+top)->row = 1;
(stack+top)->dir = 0;

if(maze_out())
{
while(i <= top)
{
printf("(%d,%d,%d)",stack[i].row,stack[i].col,stack[i].dir);
i ++;
}
// printf("(%d,%d)",EXIT_ROW,EXIT_COL);

}
/*free the memory*/
free(stack);
/*point to the NULL*/
stack = NULL;
return 1;
}

測(cè)試結(jié)果：

在迷宮問題中，棧主要實(shí)現(xiàn)了對(duì)滿足條件坐標(biāo)以及方向值(0-7,分別表示一個(gè)具體的方向)的動(dòng)態(tài)保存能夠保證路勁的一致性，也就是先入后出的特性。