题解 | #迷宫问题#

import java.util.LinkedList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int M = in.nextInt();

        int[][] maze = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                maze[i][j] = in.nextInt();
            }
        }


        LinkedList<Point> points = new LinkedList<>();
        dp(points, maze, 0, 0, 0);

        for (Point point : points) {
            System.out.println("(" + point.i + "," + point.j + ")");
        }


        // from 1: 上  2下，左 3， ,右4
    }


    public static boolean dp(LinkedList<Point> points, int[][] maze, int i, int j,
                             int from) {

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

        if (i < 0 || j < 0) {
            return false;
        }

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

        points.add(new Point(i, j));


        if (i == maze.length - 1 && j == maze[0].length - 1) {
            return true;
        }

        if (from != 4 && dp(points, maze, i, j + 1, 3)) {
            return true;
        }

        if (from != 2 && dp(points, maze, i + 1, j, 1)) {
            return true;
        }

        if (from != 1 && dp(points, maze, i - 1, j, 2)) {
            return true;
        }

        if (from != 3 && dp(points, maze, i, j - 1, 4)) {
            return true;
        }

        points.removeLast();
        return false;
    }


    public static class Point {
        int i;
        int j;

        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}