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

javalearner

/*
* 文件路径：yf.ds.c04.recursion/Maze.java
* 项目：data structures
* 创建时间：Mar 12, 2009 10:21:41 PM
* 作者：严飞（Email:boyyafee@126.com Blog:http://hi.baidu.com/boyyf QQ:43373860）
* 注意：该文件受中国相关法律保护，其著作权和知识产权归其作者所有。
*
*/
package yf.ds.c04.recursion;
    /**
* 迷宫游戏-递归的经典演示
* 该游戏中，给定了一个迷宫（一个矩阵，通过二位数组实现），从坐上角出发，只能上下左右方向前进，
* 0代表阻碍，1代表可行，若能从右下角穿出，则成功。在尝试每条路径时，若成功通过，将该路径上的1修改为7
* 若尝试了某路径而不可通，则将该路径上的1修改为3
*/
public class Maze {
private final int TRIED = 3; //尝试过而未能最终通过的路径点值
private final int PATH = 7; //成为成功路径的点值

private int[][] grid = {
     {1,1,1,0,1,1,0,0,0,1,1,1,1},
     {1,0,1,1,1,0,1,1,1,1,0,0,1},
     {0,0,0,0,1,0,1,0,1,0,1,0,0},
     {1,1,1,0,1,1,1,0,1,0,1,1,1},
     {1,0,1,0,0,0,0,1,1,1,0,0,1},
     {1,0,1,1,1,1,1,1,0,1,1,1,1},
     {1,0,0,0,0,0,0,0,0,0,0,0,0},
     {1,1,1,1,1,1,1,1,1,1,1,1,1},
}; //给出的迷宫

//从该点出发，看看该点是否形成有效路径
public boolean traverse(int row, int col) {
    boolean result = false;
   
    //如果当前点可行，这里valid()相当于给出了一个base case
    if(valid(row, col)) {
     //首先将该点改为TRIED，此时还有一个功能，就是让相邻点不会反着又走回来
     //因为valid检验时，需要检验目标点的值是否是1
     grid[row][col] = TRIED;
   
     //判断是否已经走出迷宫
     //如果已经走出，相当于给出另了一个base case
     if(row == grid.length-1 && col == grid[0].length-1) {
      result = true;
     }
     //如果没有走出，则递归的尝试朝四个方向移动
     else {
      result = traverse(row+1,col);
     
      if(!result) {
       result = traverse(row-1,col);
      }
     
      if(!result) {
       result = traverse(row,col+1);
      }
     
      if(!result) {
       result = traverse(row,col-1);
      }
     }
   
     if(result){
      grid[row][col] = PATH;
     }
       }
   
   
   
    return result;
}


//检验某个点是否可行
private boolean valid(int row, int col){
    boolean result = false;
   
    //首先检查该点是否越界
    if(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length) {
     //再检验该点的值是否是1
     //注意二位数组是行、列顺序
     if(grid[row][col] == 1 ){
      result = true;
     }
    }
   
    return result;
}


//重写toString方法
public String toString() {
    StringBuffer result = new StringBuffer("
");
    for(int i=0; i<grid.length; i++){
     for(int j=0; j<grid.length; j++){
      result.append(grid[j]);
     }
     result.append("
");
    }
   
    return result.toString();
}


public static void main(String args[]){
    Maze maze = new Maze();
    System.out.println(maze);
   
    boolean result = maze.traverse(0, 0);
    if(result) {
     System.out.println("成功穿越");
    } else {
     System.out.println("未能成功穿越");
    }
   
    System.out.println(maze);
}

运行结果：
   
C:java>java Maze
    1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111
    成功穿越
    7770110001111
3077707771001
0000707070300
7770777070333
7070000773003
7077777703333
7000000000000
7777777777777
   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/3/000104562.zip