算法之走迷宫[宝典]

算法之走迷宫[宝典] 算法之走迷宫 走迷宫游戏我想大家都玩过，利用算法解决走迷宫问题是我们要考虑的问题。 走迷宫在算法中设置一个二维数组，数组中只有0和1，0代表此路可通，1代 表此路不可通。数组初始化如下: 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 这是8*8的数组，通过观察应该有很多条路，但是算法从第一个位置开始向下找 到走出迷宫的路。 C语言算法代码如下: #include "stdafx.h" //#include"stdio.h" //#include"conio.h" int maze[8][8]={ {0,0,0,0,0,0,0,0},{0,1,1,1,1,0,1,0},{0,0,0,0,1,0,1,0},{0,1,0,0,0,0,1,0},{0,1,0,1,1,0, 1,0}, {0,1,0,0,0,0,1,1,},{0,1,0,0,1,0,0,0},{0,1,1,1,1,1,1,0} };/*存储迷宫*/ int fx[4]={1,-1,0,0}; int fy[4]={0,0,-1,1};/*控制前后上下的走法，下标起点为0*/ int i,j,k,total; void out()/*输出函数*/ { int i,j; for(i=0;i<8;i++) { for(j=0;j<8;j++) { if(maze[i][j]==3) { printf("V "); total++; } else printf("* "); } printf("\n"); } } int check(int i,int j,int k) { int flag=1; i=i+fx[k]; j=j+fy[k]; if(i<0||i>7||j<0||j>7)/*是否在迷宫内*/ flag=0; if(maze[i][j]!=0)/*是否可行*/ flag=0; return(flag); } void search(int i,int j) { int k,newi,newj; for(k=0;k<4;k++) /*搜索可达方格*/ if(check(i,j,k) == 1) { newi=i+fx[k]; newj=j+fy[k]; maze[newi][newj]=3; /*来到新位置后，设置已走变量*/ if(newi==7&&newj==7) /*如果到了出口就则输出，否则下一步递归*/ out(); else search(newi,newj); } maze[i][j]=2;/*某一方格只能走入死胡同*/ } int main() { maze[0][0]=3;/*入口坐标设置已走标志*/ search(0,0); printf("\n total is:%d",total); /*统计总步数*/ //getch(); return 0; } 运行结果如下: