题解 | #迷宫问题#

/*
 * 时间: 2021-05-18
 * 思路: DFS
 */
import java.util.*;

public class Main {
    public static final int[] dir = {1, 0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int row = sc.nextInt();
            int col = sc.nextInt();
            int[][] map = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            Deque<String> result = new LinkedList<>();
            Deque<String> output = new LinkedList<>();
            dfs(map, 0, 0, result, output);

            while (!output.isEmpty()) {
                System.out.println(output.removeLast());
            }
        }
    }

    public static void dfs(int[][] map, int i, int j, Deque<String> result, Deque<String> output) {
        if (i == map.length - 1 && j == map[0].length - 1) {
            if (output.isEmpty() || result.size() < output.size()) {
                output.clear();
                output.addAll(result);
                // 将当前节点入栈
                output.push("(" + i + "," + j + ")");
            }
            return;
        }

        if (i < 0 || i >= map.length || j < 0 || j >= map[0].length) {
            return;
        }

        if (map[i][j] == 1) {
            return;
        }

        for (int m = 0; m < 4; m++) {
            map[i][j] = 1;
            result.push("(" + i + "," + j + ")");
            dfs(map, i + dir[m], j + dir[m + 1], result, output);
            map[i][j] = 0;
            result.pop();
        }
    }
}