/*百度作个东西能用点心么 代码区的代码丑爆了 *程序的框架:宏定义，函数声明，main函数，函数实现 * ========================================================= * Filename: maze.c * Description: 基于栈寻找迷宫路径 * * ========================================================= */#include #include #include #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};/*--------------------------------------------------- * 棋盘由R*C 个节点构成，每个节点包含的信息由: * 节点位置(x,y) , 是否是死路(yes/no) , 是否被访问过(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.初始化迷宫,每个节点有4/5的概率可走 * 2.输出迷宫的构造 *---------------------------------------------------*/void Initmaze(Maze *m);void printmaze(Maze m);/*--------------------------------------------------- * 存储访问过程的栈及相应操作 *---------------------------------------------------*/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;ima[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+1ma[current_x][current_y+1])) /* rigth valid */ n=m->ma[current_x]+current_y+1; else if(current_x+1ma[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; }}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;iterp.x,s.no[iter]->p.y);}void printmaze(Maze m){ int i,j; for(i=0;ioutput:如果无路径
如果有路径.
