老鼠走迷宫.docx

1.Algorithm Gossip: 老鼠走迷官（一）说明：老鼠走迷宫是递回求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试以程式求出由入口至出口的路径。解法：老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止，这是递回的基本题。代码：#include#includeint migo77=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 starti=1,startj=1;/出发点int endi=5,endj=5;/出口int success=0;int visit(int i,int j)migoij=1;if(i=endi&j=endj)/判断有没有到出口success=1;if(success!=1&migoij+1=0) visit(i,j+1);/四种走法，右，下，左，上if(success!=1&migoi+1j=0) visit(i+1,j);if(success!=1&migoij-1=0) visit(i,j-1);if(success!=1&migoi-1j=0) visit(i-1,j);if(success!=1)migoij=0;return success;int main()int i,j;printf(显示迷宫：n);for(i=0;i7;i+)for(j=0;j7;j+)if(migoij=2)printf();elseprintf( );printf(n);if(visit(starti,startj)=0)printf(n没有找到出口！n);elseprintf(n显示路径:n);for(i=0;i7;i+)for(j=0;j7;j+)if(migoij=2)printf();else if(migoij=1)printf();elseprintf( );printf(n);return 0;2.Algorithm Gossip: 老鼠走迷官（二）说明：由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路径呢？解法求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递回就可以了，比求出单一路径还简单，我们的程式只要作一点修改就可以了。代码：#include#includeint migo99=2, 2, 2, 2, 2, 2, 2, 2, 2,2, 0, 0, 0, 0, 0, 0, 0, 2,2, 0, 2, 2, 0, 2, 2, 0, 2,2, 0, 2, 0, 0, 2, 0, 0, 2,2, 0, 2, 0, 2, 0, 2, 0, 2,2, 0, 0, 0, 0, 0, 2, 0, 2,2, 2, 0, 2, 2, 0, 2, 0, 2,2, 0, 0, 0, 0, 0, 0, 0, 2,2, 2, 2, 2, 2, 2, 2, 2, 2;/迷宫图int starti=1,startj=1;/出发点int endi=7,endj=7;/出口void visit(int i,int j)int m,n;migoij=1;if(i=endi&j=endj)/判断有没有到出口for(m=0;m9;m+)for(n=0;n9;n+)if(migomn=2)printf();else if(migomn=1)printf();elseprintf( );printf(n);if(migoij+1=0) visit(i,j+1);/四种走法，右，下，左，上if(migoi+1j=0) visit(i+1,j);if(migoij-1=0) visit(i,j-1);if(migoi-1j=0) visit(i-1,j);migoij=0;int main()int i,j;printf(显示迷宫：n);for(i=0;i