maze.c

迷宫算法（maze） /* Maze * Starting point is m[0][0], need to find a path go to m[9][9]. 0 means OK,

/* Source code for question 4 : Maze by Jerry Jiang, Mar 30 2009 */

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define MAX_X		10
#define MAX_Y		10
#define STACK_SIZE	MAX_X*MAX_Y

#define TRUE		1
#define FALSE		0
#define BOOL        int

int m[MAX_X][MAX_Y]=
{  
	{0,    1,    1,    0,    1,    1,    1,    1,    0,    1},
	{0,    1,    0,    0,    0,    0,    1,    1,    1,    1},
	{0,    1,    0,    0,    1,    0,    1,    1,    1,    1},
	{0,    0,    0,    1,    1,    0,    1,    1,    1,    1},
	{0,    1,    1,    1,    0,    0,    1,    0,    0,    1},
	{1,    1,    1,    1,    0,    1,    1,    0,    0,    1},
	{1,    1,    0,    1,    0,    0,    0,    0,    0,    1},
	{1,    1,    0,    0,    1,    1,    1,    1,    0,    1},
	{0,    1,    1,    0,    1,    1,    1,    1,    0,    1},
	{0,    1,    1,    1,    1,    1,    1,    1,    0,    0} 
};

typedef struct _maze_node
{
	int		x;
	int		y;
	BOOL    bPass;

}maze_node;

maze_node  *path_stack ; 
char       no_way_node[MAX_X*MAX_Y];
unsigned int  n_stack_top = 0;

void print_maze(int x,int y)
{
	int i , j;
	for(i = 0;i< MAX_X; i++){
		for(j = 0; j < MAX_Y; j++){
			if(( x == i )&&( y==j ))
				printf("@");   //print the mouse
			else{
				if(m[i][j])
					printf("#");
				else
					printf(" "); //print the path
			}
		}
		printf("\n");
	}
}

void init_maze_node(maze_node *node,int x0,int y0,BOOL b_pass)
{
	node->x = x0;
	node->y = y0;
	node->bPass = b_pass;
}

void copy_node(maze_node *node_dest,maze_node *node_src)
{
	node_dest->x = node_src->x;
	node_dest->y = node_src->y;
	node_dest->bPass = node_src->bPass;
}

void push_stack(maze_node *node)
{
	if(n_stack_top>STACK_SIZE){
       printf("Stack is full\n");
       return;
    }else{
		copy_node(&(path_stack[n_stack_top]),node);
		n_stack_top++;
	}
}

maze_node *pop_stack()
{
	maze_node *node = NULL;

	if(n_stack_top<=0)
		return NULL;
	else{
		node =  &path_stack[n_stack_top-1];
		n_stack_top--;
	}
	return(node);
}

maze_node *stack_back()
{
	maze_node *node = NULL;

	if(n_stack_top<=0)
		return NULL;
	else
		node =  &path_stack[n_stack_top-1];

	return(node);
}

enum Result { FAIL,PASS,SUCCESS};

BOOL exist_in_path(int x,int y)
{
	unsigned int i;
	for(i = 0; i < n_stack_top;i++){
		if((path_stack[i].x == x)&&(path_stack[i].y == y))
			return TRUE;
	}
	return FALSE;
}

int go_through_node(int x,int y)
{
	BOOL b_pass = FALSE;

	if((x < 0 || y < 0) || ((x == MAX_X)&&( y != MAX_X)) || ((x != MAX_X)&&( y == MAX_X)))   // meet the wall
		return FAIL;

	if(no_way_node[y*MAX_X + x])
		return FAIL;

	if(exist_in_path(x,y))  // in pevious path
		return FAIL;
	
	if(!m[x][y])
		b_pass = TRUE;

	maze_node node;
	init_maze_node(&node,x,y,b_pass);

	if(node.bPass){

		printf( "step[%d,%d]\n",x,y);
		print_maze(x,y);
		push_stack(&node);
		getchar();
	
		if((x == MAX_X-1) &&(y == MAX_Y-1))
			return SUCCESS;
	    if((go_through_node(node.x+1,node.y) == FAIL)
			&&(go_through_node(node.x-1,node.y) == FAIL)
			&&(go_through_node(node.x,node.y+1) == FAIL)
			&&(go_through_node(node.x,node.y-1) == FAIL))
		{
			pop_stack();
			maze_node *node = stack_back();
			x = node->x;
			y = node->y;
			no_way_node[node->y*MAX_X + node->x] = 1;
			printf( "step[%d,%d]\n",x,y);
			print_maze(x,y);
			getchar();
			return FAIL;
		}
		return PASS;

	}
	else
		return FAIL;
}

int main()
{
	print_maze(0,0);
	int x = 0,y = 0;

	memset(no_way_node,0,sizeof(no_way_node));
	path_stack = (maze_node *)malloc(sizeof(maze_node) * STACK_SIZE);
	if(path_stack == NULL)
		return;

	while(go_through_node(x,y) != SUCCESS){
			printf("I made it.Success!\n");
			break;
	}
	printf("The path for the maze:\n");
	unsigned int i;
	for(i = 0; i < n_stack_top;i++)
		printf("[%d,%d]\n",path_stack[i].x,path_stack[i].y);
	free(path_stack);

	getchar();
}