题解 | #迷宫问题# DFS

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static LinkedList<Vector2d> visited = new LinkedList<>();
    private static LinkedList<Vector2d> next = new LinkedList<>();
    private static int[][] maze;
    private static int row;
    private static int column;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] size = reader.readLine().split(" ");
        row = Integer.parseInt(size[0]);
        column = Integer.parseInt(size[1]);
        maze = new int[row][column];

        // 录入迷宫
        for (int i = 0; i < row; i++) {
            String[] next = reader.readLine().split(" ");
            for (int j = 0; j < next.length; j++) {
                maze[i][j] = Integer.parseInt(next[j]);
            }
        }

        // 设定起点
        Vector2d start = new Vector2d(0, 0);
        // 寻找最短路径
        path(start);

        // 从终点回溯输出最短路径
        output(visited.pollLast());
    }

    private static void output(Vector2d end){
        if (end != null) {
            output(end.getPrev());
            System.out.printf("(%d,%d)\n", end.getX(), end.getY());
        }
    }

    private static void path(Vector2d start) {
        // 标记当前节点为已访问并寻找下一步的路径点
        visited.add(start);
        // 将下一步所有可访问的路径点加入待访问列表
        neighbours(start);

        while (true) {
            Vector2d current = next.poll();
            visited.add(current);
            if (current.getX() == row - 1 && current.getY() == column - 1) {
                break;
            }
            neighbours(current);
        }
    }

    private static void neighbours(Vector2d v) {
        int x = v.getX();
        int y = v.getY();
        Vector2d up = new Vector2d(x - 1, y, v);
        Vector2d down = new Vector2d(x + 1, y, v);
        Vector2d left = new Vector2d(x, y - 1, v);
        Vector2d right = new Vector2d(x, y + 1, v);
        // up
        if (x - 1 >= 0 && maze[x - 1][y] == 0) {
            if (!isVisit(up)) {
                next.add(up);
            }
        }

        // down
        if (x + 1 < row && maze[x + 1][y] == 0) {
            if (!isVisit(down)) {
                next.add(down);
            }
        }

        // left
        if (y - 1 >= 0 && maze[x][y - 1] == 0) {
            if (!isVisit(left)) {
                next.add(left);
            }
        }

        // right
        if (y + 1 < column && maze[x][y + 1] == 0) {
            if (!isVisit(right)) {
                next.add(right);
            }
        }
    }

    private static boolean isVisit(Vector2d vector) {
        for (Vector2d coor : visited) {
            if (coor.equals(vector)) {
                return true;
            }
        }
        return false;
    }

    private static class Vector2d {
        private int x;
        private int y;
        private Vector2d prev;

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

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public Vector2d getPrev() {
            return prev;
        }

        public void setPrev(Vector2d prev) {
            this.prev = prev;
        }

        public boolean equals(Vector2d v) {
            return v.getX() == this.x && v.getY() == this.y ? true : false;
        }

    }
}

X是纵坐标，Y是横坐标