首页 > 代码库 > 算法：老鼠走迷宫问题
算法：老鼠走迷宫问题
算法：老鼠走迷宫问题(初)
【写在前面】
老鼠走迷宫问题的递归实现，是对递归思想的一种应用。
【问题描述】
给定一个二维数组，数组中2表示墙壁，0表示通路，由此数组可展示为一个迷宫图。给定入口位置和出口位置，判断之间是否存在通路并显示出走出迷宫的道路。
【代码】
对题目的描述部分
int migo[7][7]={{2, 2, 2, 2, 2, 2, 2},{2, 0, 0, 0, 0, 0, 2},{2, 0, 2, 0, 2, 0, 2},{2, 0, 0, 0, 0, 2, 2},{2, 2, 0, 2, 0, 2, 2},{2, 0, 0, 0, 0, 0, 2},{2, 2, 2, 2, 2, 2, 2}};//迷宫图int startX=1,startY=1;
int endX=5,endY=5;
|说明：
1.给出用来描述迷宫信息的数组。
2.给出入口和出口坐标。
递归的实现部分
int flag=0;int find(int x,int y){ migo[x][y]=1; if(x==endX&&y==endY) flag=1; if(migo[x][y+1]==0&&flag!=1) find(x,y+1); if(migo[x][y-1]==0&&flag!=1) find(x,y-1); if(migo[x+1][y]==0&&flag!=1) find(x+1,y); if(migo[x-1][y]==0&&flag!=1) find(x-1,y); if(flag!=1) migo[x][y]=0; return flag;}
|说明：
1.第一句代码 migo[x][y]=1,意义何在呢？我们在开始处把它设为1，表示我们以此为轴开始朝四周移动，每到下一个点便再以之为轴，...不段进行判断，直达我们找到通路，即flag=1。但是我们需要明白的是，一旦我们沿某条路找不到通路时，最后一句代码
便又将其还原为0，在对迷宫的所有道路探索后，我们可能会找到通路，那条路上的每一个元素便会被赋予1，如果都没有，那就不会。
2.关于递归的思路：不断以某点为轴，向四处扩散，在找到出口点便停止递归。
道路展示实现部分
int main(int argc, char **argv){ int i,j; printf("显示迷宫：\n"); for(i=0;i<7;i++) { for(j=0;j<7;j++) if(migo[i][j]==2) printf("█"); else printf(" "); printf("\n"); } if(find(startX,startY)==0) { printf("\n没有找到出口！\n"); } else { printf("\n显示路径:\n"); for(i=0;i<7;i++) { for(j=0;j<7;j++) { if(migo[i][j]==2) printf("█"); else if(migo[i][j]==1) printf("*"); else printf(" "); } printf("\n"); } } return 0;}
|说明：
略。
算法：老鼠走迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。