backtracking to find a path in maze

maze.c

/*
 * =========================================================
 *       Filename:  maze.c
 *    Description:  backtracking to find a path in maze
 *          refer:  http://blog.csdn.net/synapse7/article/details/14411365
 * =========================================================
 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define ROW 10
#define COL 10
#define STACKSIZE 100
#define ISEND(n) ((n).p.x==ROW-1 && (n).p.y==COL-1)
#define ISVALID(n) ((n).visit== NO && ((n).path== YES))
#define ISEMPTY(s) (s.top==0)
enum Bool{
    NO,
    YES
};
/*---------------------------------------------------
 *  creat our maze,a node in maze has following info:
 *  position(x,y) , path(yes/no) , visit(yes/no)
 *---------------------------------------------------*/
typedef struct point Point;
typedef struct node Node;
typedef struct maze Maze;
struct point{
    int x,y;
};
struct node{
    Point p;
    int path;
    int visit;
};
struct maze{
    Node ma[ROW][COL];
};
/*---------------------------------------------------
 *  1.initialize maze, each node has 4/5 path yes
 *  2.decide if the current maze node is valid
 *---------------------------------------------------*/
void Initmaze(Maze *m);
void printmaze(Maze m);
/*---------------------------------------------------
 *  DFS stack to store path
 *---------------------------------------------------*/
typedef struct stack Stack;
struct stack{
    Node *no[STACKSIZE];
    int top;
};
Stack s;
void push(Node * n);
Node* pop();
void print(Stack s);


/*---------------------------------------------------
 *  find path based on stack
 *---------------------------------------------------*/
int findpath(Maze *m,Node *n);

int main(){
    Maze m;
    Initmaze(&m);
    printmaze(m);
    Node *n=m.ma[0];
    if(findpath(&m,n))
        print(s);
}

void Initmaze(Maze *m){
    int i,j;
    srand(time(NULL)); /* initialize random seed */
    for(i=0;i<ROW;i++)
        for(j=0;j<COL;j++){
            m->ma[i][j].visit=NO;
            m->ma[i][j].p.x=i;
            m->ma[i][j].p.y=j;
            m->ma[i][j].path=((i==0 && j==0) || (i==ROW-1 && j==COL-1) || rand()%ROW < 4*ROW/5)?YES:NO;
        }
}

int findpath(Maze *m,Node *n){
    while(!ISEND(*n)){
        if(n->visit==NO){
            n->visit=YES;
            push(n);
        }
        int current_x=n->p.x;
        int current_y=n->p.y;
        if(current_y+1<COL && ISVALID(m->ma[current_x][current_y+1])) /* rigth valid */
            n=m->ma[current_x]+current_y+1;
        else if(current_x+1<ROW && ISVALID(m->ma[current_x+1][current_y])) /* down valid */
            n=m->ma[current_x+1]+current_y;
        else if(current_x-1>=0 && ISVALID(m->ma[current_x-1][current_y])) /* up valid */
            n=m->ma[current_x-1]+current_y;
        else if(current_y-1>=0 && ISVALID(m->ma[current_x][current_y-1])) /* left valid */
            n=m->ma[current_x]+current_y-1;
        else{
            pop(); /* current n is not valid */
            if(!ISEMPTY(s)) /* n point to pre */
                n=s.no[s.top-1];
            else{
                printf("stack empty.\n");
                n=NULL;
                break;
            }
        }
    }
    if(n==NULL)
        return 0;
    else{
        push(n);
        return 1;
    }

}
/*
int DFS(Maze *m , Node *n){
    if(Isvalid(*n)){
        if(n->p.x==ROW-1 && n->p.y==COL-1){ 
            printf("%d %d\n",ROW-1,COL-1);
            push(n);
            return 1;
        }
        n->visit=YES;
        push(n);
        int current_x=n->p.x;
        int current_y=n->p.y;
        printf("%d %d\n",current_x,current_y);
        if(current_x!=ROW-1 && current_y!=COL-1){
            DFS(m,m->ma[current_x]+current_y+1);
            DFS(m,m->ma[current_x+1]+current_y);
        }
        else if(current_x==ROW-1)
            DFS(m,m->ma[current_x]+current_y+1);
        else
            DFS(m,m->ma[current_x+1]+current_y);
        pop();
    }
    return 0;
}*/

void push(Node * n){
    s.no[s.top++]=n;
}
Node * pop(){
    if(s.top!=0)
        return s.no[--s.top];
    else{
        printf("%s","stack empty\n");
        return NULL;
    }
}

void print(Stack s){
    int iter;
    for(iter=0;iter<s.top;iter++)
        printf("%d %d\n",s.no[iter]->p.x,s.no[iter]->p.y);
}
void printmaze(Maze m){
    int i,j;
    for(i=0;i<ROW;i++)
        for(j=0;j<COL;j++)
            printf("%d%s",m.ma[i][j].path,(j==COL-1)?"\n":" ");
}

we may want to create maze by user's input.
dynamic alloc two dim array.
m->ma=malloc(ROW_sizeof(int *));
for(i=0;i<ROW;i++)
m->ma[i]=malloc(COL_sizeof(int));

递归与栈的转化 对比refer