题解 | #迷宫问题#

import java.util.*;

public class Main {
    static int k;//记录前进的步数
    static int targetRow;//记录前进的步数
    static int targetCol;//记录前进的步数
    static boolean[][] booleans;//记录当前位置已经走过

    static ArrayList<ArrayList<String>> list;//记录前进路线
    static ArrayList<String> temp;//记录当前路线
    static int[][] arr;//记录路线图

    //0,0->n,n
    public static void main(String[] args) {
        //读取数据
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col = in.nextInt();
        arr = new int[row][col];
        booleans = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        //初始化
        temp = new ArrayList<>();
        list = new ArrayList<>();
        targetRow = row - 1;
        targetCol = col - 1;
        booleans[0][0] = true;
        temp.add("(0,0)");
        sdf1(0, 0);
        ArrayList<String> list11 = list.get(0);
        for (int i = 0; i < list11.size(); i++) {
            System.out.println(list11.get(i));
        }
    }

    private static void sdf1(int row, int col) {
        if (row == targetRow && col == targetCol) {
            ArrayList<String> listTemp = new ArrayList<>(temp);
            list.add(listTemp);
            return;
        }
        int row1 = row + 1;//下面一格
        int row2 = row - 1;//上面一格
        int col1 = col + 1;//右面一格
        int col2 = col - 1;//左面一格
        if (col1 <= targetCol && arr[row][col1] == 0 && !booleans[row][col1]) {
            temp.add("(" + row + "," + col1 + ")");
            booleans[row][col1] = true;
            sdf1(row, col1);
            temp.remove("(" + row + "," + col1 + ")");
            booleans[row][col1] = false;
        }
        if (row1 <= targetRow && arr[row1][col] == 0 && !booleans[row1][col]) {
            temp.add("(" + row1 + "," + col + ")");
            booleans[row1][col] = true;
            sdf1(row1, col);
            temp.remove("(" + row1 + "," + col + ")");
            booleans[row1][col] = false;
        }
        if (col2 >= 0 && arr[row][col2] == 0 && !booleans[row][col2]) {
            temp.add("(" + row + "," + col2 + ")");
            booleans[row][col2] = true;
            sdf1(row, col2);
            temp.remove("(" + row + "," + col2 + ")");
            booleans[row][col2] = false;
        }
        if (row2 >= 0 && arr[row2][col] == 0 && !booleans[row2][col]) {
            temp.add("(" + row2 + "," + col + ")");
            booleans[row2][col] = true;
            sdf1(row2, col);
            temp.remove("(" + row2 + "," + col + ")");
            booleans[row2][col] = false;
        }
    }
}

解题思路:

1, 因为只有一条正确路径, 因此可以按照最优深度搜索方法进行求解;

2, 使用最优深度搜索时, 需要注意边界的控制, 并记录下已经走过的路径, 避免路径重复