题解 | 迷宫问题

回溯法找到终点坐标即返回结果

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

public class Main {
    private static int H = 0;
    private static int W = 0;
    private static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        int[][] board = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        List<List<int[]>> result = new ArrayList<>();
        List<int[]> pathList = new ArrayList<>();
        boolean[][] visited = new boolean[H][W];
        visited[0][0] = true;
        pathList.add(new int[]{0, 0});
        dfs(board, 0, 0, pathList, result, visited);
        if (!result.isEmpty()) {
            List<int[]> path = result.get(0);
            for (int i = 0; i < path.size(); i++) {
                int[] pos = path.get(i);
                System.out.println("(" + pos[0] + "," + pos[1] + ")");
            }
        }
    }

    private static void dfs(int[][] board,int row,int col, List<int[]> pathList, List<List<int[]>> resultList, boolean[][] visited) {
        if (row == H - 1 && col == W - 1) {
            resultList.add(new ArrayList<>(pathList));
            return;
        }
        for (int[] dir : DIRS) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (newRow >= 0 && newRow < H && newCol >= 0 && newCol < W && !visited[newRow][newCol] && board[newRow][newCol] == 0) {
                visited[newRow][newCol] = true;
                pathList.add(new int[]{newRow, newCol});
                dfs(board, newRow, newCol, pathList, resultList, visited);
                pathList.remove(pathList.size() - 1);
                visited[newRow][newCol] = false;
            }
        }
    }
}