Go语言视频零基础入门到精通

javalearner

说明
   老鼠走迷宫是递归求解的基本题型，我们在二维数组中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径，试用程序求出由入口至出口的路径。  

解法
    老鼠的走法有上、左、下、右四个方向，在每前进一格之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在二维数组阵列中依序测试四个方向，直到走到出口为止，这是递归的基本题，请直接看程序就可以理解。

public class Mouse {  
     private int startI, startJ;  // 入口   
     private int endI, endJ;  // 出口  
     private boolean success = false;   
  
   
   
     
   

   
   
  

     public static void main(String[] args) {  
         int[][] maze = {{2, 2, 2, 2, 2, 2, 2},   
                         {2, 0, 0, 0, 0, 0, 2},   
                         {2, 0, 2, 0, 2, 0, 2},   
                         {2, 0, 0, 2, 0, 2, 2},   
                         {2, 2, 0, 2, 0, 2, 2},   
                         {2, 0, 0, 0, 0, 0, 2},   
                         {2, 2, 2, 2, 2, 2, 2}};  
           
         System.out.println("显示迷宫：");   
         for(int i = 0; i < maze.length; i++) {   
             for(int j = 0; j < maze[0].length; j++)   
                 if(maze[j] == 2)   
                     System.out.print("■");   
                 else   
                     System.out.print("  ");   
             System.out.println();   
         }  

         Mouse mouse = new Mouse();  
         mouse.setStart(1, 1);  
         mouse.setEnd(5, 5);  
           
         if(!mouse.go(maze)) {  
             System.out.println("
没有找到出口！");  
         }  
         else {  
             System.out.println("
找到出口！");  
             for(int i = 0; i < maze.length; i++) {   
                 for(int j = 0; j < maze[0].length; j++) {   
                     if(maze[j] == 2)   
                         System.out.print("■");   
                     else if(maze[j] == 1)   
                         System.out.print("◇");   
                     else   
                         System.out.print("  ");   
                 }   
                 System.out.println();   
             }              
         }  
     }  
      
     public void setStart(int i, int j) {  
         this.startI = i;  
         this.startJ = j;  
     }  
      
     public void setEnd(int i, int j) {  
         this.endI = i;  
         this.endJ = j;  
     }  
      
     public boolean go(int[][] maze) {  
         return visit(maze, startI, startJ);  
     }  
      
     private boolean visit(int[][] maze, int i, int j) {  
         maze[j] = 1;   

         if(i == endI && j == endJ)   
             success = true;   

         if(!success && maze[j+1] == 0)   
             visit(maze, i, j+1);   
         if(!success && maze[i+1][j] == 0)  
             visit(maze, i+1, j);   
         if(!success && maze[j-1] == 0)  
             visit(maze, i, j-1);   
         if(!success && maze[i-1][j] == 0)  
             visit(maze, i-1, j);   

         if(!success)   
             maze[j] = 0;   
           
         return success;   
     }  
  }  



   由于迷宫的设计，老鼠走迷宫的入口至出口路径可能不只一条，如何求出所有的路径呢？
   求所有路径看起来复杂但其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递归就可以了，比求出单一路径还简单，我&#65533;的程序只要作一点修改就可以了。  
  public class Mouse {  
     private int startI, startJ;  // 入口   
     private int endI, endJ;  // 出口  
      
     public static void main(String[] args) {  
         int maze[][] = {{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(int i = 0; i < maze.length; i++) {   
             for(int j = 0; j < maze[0].length; j++)   
                 if(maze[j] == 2)   
                     System.out.print("■");   
                 else   
                     System.out.print("  ");   
             System.out.println();   
         }  

         Mouse mouse = new Mouse();  
         mouse.setStart(1, 1);  
         mouse.setEnd(7, 7);  
           
         mouse.go(maze);  
     }  
      
     public void setStart(int i, int j) {  
         this.startI = i;  
         this.startJ = j;  
     }  
      
     public void setEnd(int i, int j) {  
         this.endI = i;  
         this.endJ = j;  
     }  
      
     public void go(int[][] maze) {  
         visit(maze, startI, startJ);  
     }  
      
     private void visit(int[][] maze, int i, int j) {  
         maze[j] = 1;   

         if(i == endI && j == endJ) {  
             System.out.println("
找到出口！");  
             for(int m = 0; m < maze.length; m++) {   
                 for(int n = 0; n < maze[0].length; n++) {   
                     if(maze[m][n] == 2)   
                         System.out.print("■");   
                     else if(maze[m][n] == 1)   
                         System.out.print("◇");   
                     else   
                         System.out.print("  ");   
                 }   
                 System.out.println();  
             }  
         }  

         if(maze[j+1] == 0)   
             visit(maze, i, j+1);   
         if(maze[i+1][j] == 0)  
             visit(maze, i+1, j);   
         if(maze[j-1] == 0)  
             visit(maze, i, j-1);   
         if(maze[i-1][j] == 0)  
             visit(maze, i-1, j);   
         
         maze[j] = 0;  
     }  
  }