HJ43 迷宫问题 | 题解

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    private static Stack<int[]> path;
    private static ArrayList<int[]> minPath;
    private static int[][] map;
    private static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int row = sc.nextInt();
            int col = sc.nextInt();
            path = new Stack<>();
            minPath = null;
            map = new int[row][col];
            visited = new boolean[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            helper(0, 0);
            for (int[] p : minPath) {
                System.out.println("(" + p[0] + "," + p[1] + ")");
            }
        }
    }

    private static void helper(int i, int j) {
        if (i > map.length - 1 || i < 0 || j > map[0].length - 1 || j < 0 || visited[i][j] || map[i][j] == 1 || (minPath != null && path.size() >= minPath.size()))
            return;
        if (i == map.length - 1 && j == map[0].length - 1) {
            path.add(new int[]{i, j});
            minPath = new ArrayList<>(path);
            path.pop();
            return;
        }
        path.add(new int[]{i, j});
        visited[i][j] = true;
        for (int[] dir : dirs) {
            helper(i + dir[0], j + dir[1]);
        }
        visited[i][j] = false;
        path.pop();
    }
}