题解 | #迷宫问题#回溯算法#

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int width = in.nextInt();
        int[][] nums = new int[width][row];
        for(int i=0;i<row;i++){
            for(int j=0;j<width;j++){
                nums[j][i] = in.nextInt();
            }
        }
        /**
         * 输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。
         * 数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
         * 数据范围：2≤n,m≤10  ， 输入的内容只包含0≤val≤1
         */

        //题目要求从左上角开始走，也就是起始坐标一定是0,0
        //如果不一定从左上角开始走，此处可以改为遍历nums[][0],从碰到的第一个0开始走
        LinkedList<String> path = new LinkedList<>();
        path.add("(0,0)");
        nums[0][0] = 1;
        walk(path,0,0,nums);

        //题目保证有且只有一个走法
        List<String> list = res.get(0);
        for(String s : list){
            System.out.println(s);
        }
    }

    /**
     * 右，下，左，上 4个方向的坐标变化
     */
    static int[][] directions = {{1,0},{0,1},{-1,0},{0,-1}};
    static List<List<String>> res = new ArrayList<>();
    /**
     * @param path 已经走过的路
     * @param x 当前所在位置
     * @param y
     * @param nums 迷宫
     */
    private static void walk(LinkedList<String> path, int x, int y, int[][]nums){
        //结束条件：到达右下角
        if((x == nums.length-1) && (y == nums[0].length-1)){
            List<String> copy = new ArrayList<>();
            copy.addAll(path);
            res.add(copy);
            return;
        }

        //遍历选择：上下左右
        for(int[] direction : directions){

            int newx = x + direction[0];
            int newy = y + direction[1];
            if(0<= newx && newx  < nums.length
                && 0<= newy && newy < nums[0].length
                && nums[newx][newy] == 0){
                //记录走过的位置用于结果输出 如果只是判断迷宫能不能走出去就不需要记录了
                path.add("(" + newy + "," + newx +")");
                nums[newx][newy] = 1;//标记这个位置走过了，免得走回头路

                walk(path,newx,newy,nums);

                //撤销选择
                path.removeLast();
                nums[newx][newy] = 0;
            }
        }
    }
}