题解 | #迷宫问题#

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] lengths = line.split(" ");
        int rows = Integer.parseInt(lengths[0]);
        int cols = Integer.parseInt(lengths[1]);
        int[][] map = new int[rows][cols];
        List<String> paths = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            line = br.readLine();
            String[] vals = line.split(" ");
            for (int j = 0; j < cols; j++) {
                map[i][j] = Integer.parseInt(vals[j]);
            }
        }
        dfs(map,paths,0,0);
        for(String path : paths){
            System.out.println(path);
        }
    }

    public static boolean dfs(int[][] map,List<String> paths,int x,int y){
        paths.add("(" + x + "," + y + ")");
        map[x][y] = 1;
        if(x == map.length - 1 && y == map[0].length - 1){
            return true;
        }
        //向右
        if(y + 1 < map[0].length && map[x][y + 1] != 1 ){
            if(dfs(map,paths,x,y + 1)){
                return true;
            }
        }
        //向下
        if(x + 1 < map.length && map[x + 1][y] != 1 ){
            if(dfs(map,paths,x + 1,y)){
                return true;
            }
        }
        //向左
        if(y - 1 >= 0 && map[x][y - 1] != 1 ){
           if(dfs(map,paths,x,y - 1)){
                return true;
           }
        }
        //向上
        if(x - 1 >= 0 && map[x - 1][y] != 1 ){
            if(dfs(map,paths,x - 1,y)){
                return true;
           }
        }
        //回溯
        paths.remove(paths.size() - 1);
        map[x][y] = 0;
        return false;
    }
}

1. 题目中说到“总会有存在唯一一条路线”，想到用DFS解法(递归实现)。
2. 需要的变量包括：二维数组（模拟地图），ArrayList<String>（记录路径），
3. 递归三部曲：
1. 参数和返回值：二维数组（模拟地图），ArrayList<String>（记录路径），当前的x,y坐标 -- 4个参数；是否找到出口的Boolean--返回值
2. 截止条件：当前坐标是地图出口的坐标，则说明此时已经走出地图。
3. 单层循环逻辑：
1. 截止条件判断前，需要先把当前节点加入到ArrayList<String>中，并且在map地图中将当前的位置设置为1（有障碍），防止之后的递归中重走之前走过的路。
2. 在条件判断之后，需要递归尝试向上下左右方向试探一个单元格，并且在尝试前需要判断是否可以这样走：判断依据有两个：1.要走到的单元格不能为1（不能是障碍）2.不能走出边界
3. 如果当其中任何一个判断返回为true时，则立即返回true。
4. 最终如果四个方向上的判断都失败则回溯，将当前访问的节点从ArrayList中删除，并且在map中将当前节点设置回0。并且返回false,表示这条路的尝试失败。
4. 易错点：
1. 当在单层循环逻辑中进行上下左右方向试探时，只有当递归dfs()返回true时，才能在当前方法中立即返回true,遇到dfs()返回false时不能在当前方法中立即返回false，因为一次方向上试探的失败不能证明当前这个节点就是错误路径上的节点；只有当四个方向的尝试都失败，才能证明这个节点是在错误路径上的节点，需要从ArrayList中删除。