老鼠走迷官(二) java,c实现

FromGossip@caterpillarAlgorithmGossip:老鼠走迷官（二）說明由於迷宮的設計，老鼠走迷宮的入口至出口路徑可能不只一條，如何求出所有的路徑呢？解法求所有路徑看起來複雜但其實更簡單，只要在老鼠走至出口時顯示經過的路徑，然後退回上一格重新選擇下一個位置繼續遞迴就可以了，比求出單一路徑還簡單，我們的程式只要作一點修改就可以了。演算法ProcedureGO(maze[])[VISIT(maze,STARTI,STARTJ);]ProcedureVISIT(maze[],i,j)[maze[i][j]=1;IF(i==ENDIANDj==ENDJ)[//FINDAROUTE,PRINTTHEROUTE]IF(maze[i][j+1]==0)VISIT(maze,i,j+1);IF(maze[i+1][j]==0)VISIT(maze,i+1,j);IF(maze[i][j-1]==0)VISIT(maze,i,j-1);if(maze[i-1][j]==0)VISIT(maze,i-1,j);maze[i][j]=0;]實作C#includestdio.h#includestdlib.hvoidvisit(int,int);intmaze[9][9]={{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,2,2},{2,0,0,0,0,0,0,0,2},{2,2,2,2,2,2,2,2,2}};intstartI=1,startJ=1;//入口intendI=7,endJ=7;//出口intmain(void){inti,j;printf(顯示迷宮：\n);for(i=0;i7;i++){for(j=0;j7;j++)if(maze[i][j]==2)printf(█);elseprintf();printf(\n);}visit(startI,startJ);return0;}voidvisit(inti,intj){intm,n;maze[i][j]=1;if(i==endI&&j==endJ){printf(\n顯示路徑：\n);for(m=0;m9;m++){for(n=0;n9;n++)if(maze[m][n]==2)printf(█);elseif(maze[m][n]==1)printf(◇);elseprintf();printf(\n);}}if(maze[i][j+1]==0)visit(i,j+1);if(maze[i+1][j]==0)visit(i+1,j);if(maze[i][j-1]==0)visit(i,j-1);if(maze[i-1][j]==0)visit(i-1,j);maze[i][j]=0;}JavapublicclassMouse{privateintstartI,startJ;//入口privateintendI,endJ;//出口publicstaticvoidmain(String[]args){intmaze[][]={{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,2,2},{2,0,0,0,0,0,0,0,2},{2,2,2,2,2,2,2,2,2}};System.out.println(顯示迷宮：);for(inti=0;imaze.length;i++){for(intj=0;jmaze[0].length;j++)if(maze[i][j]==2)System.out.print(█);elseSystem.out.print();System.out.println();}Mousemouse=newMouse();mouse.setStart(1,1);mouse.setEnd(7,7);mouse.go(maze);}publicvoidsetStart(inti,intj){this.startI=i;this.startJ=j;}publicvoidsetEnd(inti,intj){this.endI=i;this.endJ=j;}publicvoidgo(int[][]maze){visit(maze,startI,startJ);}privatevoidvisit(int[][]maze,inti,intj){maze[i][j]=1;if(i==endI&&j==endJ){System.out.println(\n找到出口！);for(intm=0;mmaze.length;m++){for(intn=0;nmaze[0].length;n++){if(maze[m][n]==2)System.out.print(█);elseif(maze[m][n]==1)System.out.print(◇);elseSystem.out.print();}System.out.println();}}if(maze[i][j+1]==0)visit(maze,i,j+1);if(maze[i+1][j]==0)visit(maze,i+1,j);if(maze[i][j-1]==0)visit(maze,i,j-1);if(maze[i-1][j]==0)visit(maze,i-1,j);maze[i][j]=0;}}