回溯法解决迷宫问题

淡淡的烟草味﹌ 2022-09-30 10:51 171阅读 0赞

import java.awt.Point;
    import java.util.ArrayList;
    
    /*回溯法走迷宫
     * 定义一个二维数组：
    
    int maze[5][5] = {
    
    	0, 1, 0, 1, 0,
    
    	0, 1, 0, 1, 0,
    
    	0, 0, 0, 0, 0,
    
    	0, 1, 1, 1, 0,
    
    	0, 0, 0, 1, 0,
    
    };
    
    它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 
    
    输入:
    
    一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。 
    输出:
    
    左上角到右下角的最短路径，格式如样例所示。
    
    样例输入:
    
    0 1 0 1 0
    0 1 0 1 0
    0 0 0 0 0
    0 1 1 1 0
    0 0 0 1 0
    
    样例输出:
    
    (0, 0)
    (1, 0)
    (2, 0)
    (2, 1)
    (2, 2)
    (2, 3)
    (2, 4)
    (3, 4)
    (4, 4)
     */
    
    public class Maze {
    	 private int[][] maze;
    	 private int maxLine= 5;
    	 private int maxRow= 5;
    	 private ArrayList<Point> list=null;
    	 
    	 public static void main(String[] args) {
    		 new Maze().initialise();
    	}
    	 private void initialise(){
    		 maze=new int[][] {
    					{0, 1, 0, 1, 0},
    					{0, 1, 0, 1, 0},
    					{0, 0, 0, 0, 0},
    					{0, 1, 1, 1, 0},
    					{0, 0, 0, 1, 0},
    				};
    		list=new ArrayList<Point>();
    		check(0, 0);
    		 
    	 }
    	 private void check(int i,int j){
    		 if(i==maxRow-1&&j==maxLine-1)
    		 {
    			print();
    			return;
    		 }
    		 //向上走
    		 if(canMove(i, j, i-1, j)){
    			 Point p=new Point(i, j);
    			 maze[i][j]=-1;
    			 list.add(p);
    			 check(i-1, j);
    			 maze[i][j]=0;
    			 list.remove(p);
    		 }
    		 //向下走
    		 if(canMove(i, j, i+1, j)){
    			 Point p=new Point(i, j);
    			 maze[i][j]=-1;
    			 list.add(p);
    			 check(i+1, j);
    			 maze[i][j]=0;
    			 list.remove(p);
    		 }
    		 //向左走
    		 if(canMove(i, j, i, j-1)){
    			 Point p=new Point(i, j);
    			 maze[i][j]=-1;
    			 list.add(p);
    			 check(i, j-1);
    			 maze[i][j]=0;
    			 list.remove(p);
    		 }
    		 //向右走
    		 if(canMove(i, j, i, j+1)){
    			 Point p=new Point(i, j);
    			 maze[i][j]=-1;
    			 list.add(p);
    			 check(i, j+1);
    			 maze[i][j]=0;
    			 list.remove(p);
    		 }
    	 }
    	 
    	 private boolean canMove(int i,int j,int targetI,int targetJ){
    		 if(targetI<0||targetJ<0||targetI>maxRow-1||targetJ>maxLine-1)
    			 return false;
    		 if(maze[targetI][targetJ]==1)
    			 return false;
    		 if(maze[targetI][targetJ]==-1)
    			 return false;
    		 return true;
    	 }
    	 
    	 private void print(){
    		 for (Point point : list) 
    			System.out.println("("+(int)point.getX()+", "+(int)point.getY()+")");
    		 System.out.println("(4, 4)");
    	 }
    }