题解 | 迷宫问题

使用深度优先搜索（DFS）

import java.io.*;
import java.util.*;

public class Main {
    private static final int MAX_SIZE = 1000;
    public static int m;
    public static int n;
    public static int[][] maze = new int[MAX_SIZE][MAX_SIZE];
    public static boolean[][] visited = new boolean[MAX_SIZE][MAX_SIZE];
    private static List<Position> result;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter out = new PrintWriter(System.out)) {
            StreamTokenizer in = new StreamTokenizer(br);
            while (in.nextToken() != StreamTokenizer.TT_EOF) {
                m = (int) in.nval;
                in.nextToken();
                n = (int) in.nval;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        in.nextToken();
                        maze[i][j] = (int) in.nval;
                    }
                }
                List<Position> path = new ArrayList<>();
                path.add(new Position(0, 0));
                visited[0][0] = true;
                result = null;
                dfs(0, 0, path);
                if (result != null) {
                    for (Position p : result) {
                        out.println("(" + p.x + "," + p.y + ")");
                    }
                }
                out.flush();
                out.close();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static final int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private static void dfs(int i, int j, List<Position> path) {
        if (i == m - 1 && j == n - 1) {
            result = new ArrayList<>(path);
            return;
        }
        for (int[] d : direction) {
            int x = i + d[0];
            int y = j + d[1];
            if (x < m && x >= 0 && y < n && y >= 0 && maze[x][y] == 0 &&!visited[x][y]) {
                visited[x][y] = true;
                path.add(new Position(x, y));
                dfs(x, y, path);
                path.remove(path.size() - 1);
            }
        }
    }

    private static class Position {
        public int x;
        public int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}