爪哇国新游记之二十六----迷宫寻路

class Position{
    int x;
    int y;
    
    public Position(int x,int y){
        this.x=x;
        this.y=y;
    }
}
// 迷宫寻路
public class Maze{
    private int size;
    private int[][] matrix;// 代表迷宫的二维数组，0表示通路
    
    /**
     * 构建迷宫
     * 迷宫的左上角为入口，右下角为出口
     * @param size 二维数组的边长
     * @param percent 可通过区域占整体的比例 
     */
    public void build(int size,double percent){
        this.size=size;
        matrix=new int[size][size];
        
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                double seed=Math.random();
                
                if(seed>percent){
                    matrix[i][j]=0;
                }else{
                    matrix[i][j]=1;
                }
            }
        }
        
        // 入口出口不能堵死
        matrix[0][0]=0;
        matrix[size-1][size-1]=0;
    }
    
    // 打印迷宫
    public void displayMatrix(){
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(matrix[i][j]==0){
                    System.out.print("");// 可通过区域
                }else if(matrix[i][j]==1){
                    System.out.print("");// 不可通过区域
                }else if(matrix[i][j]==2){
                    System.out.print("⊙");// 路径
                }
            }
            
            System.out.println();
        }
    }
    
    // 寻找迷宫出路
    public boolean findPath(){
        // 暂存matrix
        int[][] arr=new int[size][size];
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                arr[i][j]=matrix[i][j];
            }
        }
        
        //  用于记住路径的栈
        Stack<Position> stack=new Stack<Position>(Position.class,size*size);
        
        matrix[0][0]=1;
        Position curr=new Position(0,0);
        stack.push(curr);
        
        while(curr.x!=size-1 || curr.y!=size-1){
            Position next=getWayout(curr);
            
            if(next!=null){
                stack.push(curr);
                
                matrix[next.x][next.y]=1;
                curr=next;
            }else{
                if(stack.isEmpty()){
                    return false;
                }else{
                    curr=stack.pop();
                }
            }
        }
        
        // matrix 取回原值
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                matrix[i][j]=arr[i][j];
            }
        }
        
        // 栈内容
        while(stack.isEmpty()==false){
            Position pos=stack.pop();
            
            matrix[pos.x][pos.y]=2;
        }
        
        matrix[size-1][size-1]=2;// 最终到达右下角
        
        return true;
    }
    
    // 取得临近能出去的点
    private Position getWayout(Position currPos){
        // 右
        if(currPos.x+1<size && matrix[currPos.x+1][currPos.y]==0){
            return new Position(currPos.x+1,currPos.y);
        }
        
        // 下
        if(currPos.y+1<size && matrix[currPos.x][currPos.y+1]==0){
            return new Position(currPos.x,currPos.y+1);
        }
        
        // 左
        if(0<currPos.x-1 && matrix[currPos.x-1][currPos.y]==0){
            return new Position(currPos.x-1,currPos.y);
        }
        
        // 上
        if(0<currPos.y-1 && matrix[currPos.x][currPos.y-1]==0){
            return new Position(currPos.x,currPos.y-1);
        }
        
        return null;
    }
    
    public static void main(String[] args){
        Maze m=new Maze();
        m.build(10, 0.3);
        System.out.println("迷宫图示");
        m.displayMatrix();
        
        boolean f=m.findPath();
        if(f){
            System.out.println("迷宫走得通，下图圆点为路径");
            m.displayMatrix();
        }else{
            System.out.println("迷宫走不通");
        }
    }
}

迷宫图示










迷宫走得通，下图圆点为路径
⊙
⊙
⊙
⊙
⊙
⊙⊙⊙
⊙
⊙⊙⊙⊙
⊙
⊙⊙⊙⊙⊙

迷宫图示










迷宫走不通