迷宫的实现

#include <stdio.h> #define N1 10 #define N2 10 int getpath(int maze[N1][N2]) //寻找路径函数 { int stack[N1*N2][2]; //保存已经走了的状态 int i,x=1,y=0,ok,top=0; stack[top][0]=x; stack[top][1]=y; //记录初始状态 while(1) { //当前点是x,y ok=0; //是否能向下一步走 if(maze[x][y+1]==0) {y=y+1;ok=1;} //如果能向下,那么给出下一个位置 else if(maze[x+1][y]==0) {x=x+1;ok=1;} else if(maze[x-1][y]==0) {x=x-1;ok=1;} else if(maze[x][y-1]==0) {y=y-1;ok=1;} if(!ok) { //如果无路可走,回到上一步 top--; if(top==0) { printf("no way!!"); return 0; } x=stack[top][0]; y=stack[top][1]; } else { //当前点是在前面的if判断中求出的下一个可以到的点 //把这个点标记为已经走过 maze[x][y]=2; top++; stack[top][0]=x;stack[top][1]=y; //把这个点放到历史路径中 if(x==N1-1 ||y==N2-1) { //如果这个点是出口,那么打印 printf("the way is:\n"); for (i=0;i <top;i++) { printf("(%d,%d)----->",stack[i][0],stack[i][1]); } printf("\n%d,%d)\n",stack[top][0],stack[top][1]); return 1; } } } } void printmaze(int maze[N1][N2]) //打印路径 { int i,j; printf("mi gong shu zhu wei:\n"); for(i=0;i <N1;i++) { for(j=0;j <N2;j++) printf("%2d",maze[i][j]); printf("\n"); } } void main() { int A[N1][N2]={1,1,1,1,1,1,1,1,1,1, 0,0,0,1,0,0,0,1,0,1, 1,1,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,0, 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,0, 1,1,1,1,1,1,1,1,1,1,}; printmaze(A); getpath(A); }