题解 | #迷宫问题#

一个递归搞定

因为输出的时候是先输出入口，然后输出路径到出口，

因此递归的时候我是从出口找入口，一旦找到就递归打印。

在每个位置，都有四个方向可以走，我们只需要判断，这个位置是不是墙，有没有走到迷宫外面，如果走到了返回false

同时还需要保证它不可以往回走，因此走过之后我们就要把它标记为 1 ， 和墙一样都不可以走。如果返回了false，证明这次路不可以通过，那么我们就需要把 这个标记为墙的之再还原成原来的值，保证下一次递归的时候不受影响

import java.util.Scanner;
// 递归
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int a = in.nextInt();
            int b = in.nextInt();
//             初始化迷宫
            int[][] da = new int[a][b];
            for(int i = 0 ; i <a ; i ++){
               for(int j = 0 ; j < b ; j ++){
                   da[i][j] = in.nextInt();
               } 
            }
//             通过递归去打印出路,通过在出口位置找入口位置
            dfs(da,a-1,b-1);
        }
    }
    
    public static boolean dfs(int[][] da,int i,int j){
        //如果 非法走出了迷宫或者 当前位置是墙 这返回fasle
        if( i<0 ||j <0 || i > da.length-1 || j >da[0].length-1 ||da[i][j] == 1 ){
            return false;
        }
//         记录当前位置，将当前位置标记为 墙，防止往回走。
        int temp = da[i][j];
        da[i][j] = 1;
//         如果当前位置是出口，或者是从当前位置向四个方向走可以可以到达出口，
//         就打印当前位置，并返回true
        if( (i == 0 && j==0) ||
            dfs(da,i-1,j) || dfs(da,i,j-1) || dfs(da,i,j+1) || dfs(da,i+1,j) ){
            System.out.println("("+i+","+j+")");
            return true;
        }
//         如果执行到这里，证明没有进入if语句，也就是此路不通，
//         还原当时为了防止往回走，而将当前位置设置成墙。
        da[i][j] = temp;
//         再返回fase 告诉上一个位置，此路不通。
        return false;
        
    }
}