求迷宫的最短路径 C语言代码.doc

《求迷宫的最短路径 C语言代码.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、/*date:2011-03-16direction:<球迷宫的最短路径>规定：数字为0时可以通过，为1时不能通过，可以斜着走。测试数据：input：68011101111010101001001111011100111001100001100110output：(6,8)(5,7)(4,6)(4,5)(3,4)(3,3)(2,2)(1,1)*/#include#definer64#definem210#definen210intm,n;typedefstruct{intx,y;//行、列坐标intpre;//链

2、域}sqtype;sqtypesq[r];//作为队列的存储空间，记录被访问过的点structmoved{intx,y;//坐标增量，取值-1，0，1};structmovedmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};intmaze[m2][n2];//迷宫数组voidPRINTPATH(sqtypesq[],intrear)//打印输出最短路径{inti=rear;do{printf("(%d,%d)",sq[i].x,sq[i].y);i

3、=sq[i].pre;}while(i!=0);printf("");}intSHORTPATH(intmaze[m2][n2])//找迷宫maze的最短路径{inti,j,v,front,rear,x,y;sq[1].x=1;sq[1].y=1;sq[1].pre=0;front=1;rear=1;maze[1][1]=-1;//标记入口点已经到达while(front<=rear)//队列非空{x=sq[front].x;y=sq[front].y;//(x，y)为出发点for(v=0;v<8;v++)//搜索(x,y)的

4、8个相邻点(i,j)是否可到达{i=x+move[v].x;j=y+move[v].y;if(maze[i][j]==0)//(i,j)为可到达点，将其入队{rear++;sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front;maze[i][j]=-1;//标记(i,j)已到达过的点}if((i==m)&&(j==n))//到达出口{PRINTPATH(sq,rear);//打印路径//RESTORE(maze);//恢复迷宫return1;//成功，返回1}}front++;//出队，fron

5、t指向新的出发点}//队空循环结束return0;//迷宫无路径，返回0}voidmain(){inti,j;printf("inputtherow,column:");scanf("%d%d",&m,&n);for(i=0;i

6、

7、i==m+1

8、

9、j==0

10、

11、j==n+1)maze[i][j]=-1;elsescanf("%d",&maze[i][j]);SHORTPATH(maze);}