题解 | #迷宫问题#

import java.util.*;

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();
            }
        }
        List<Point> road = new ArrayList<Point>();
        road.add(new Point(0, 0));
        //深度优先搜索dfs
        findNext(maze, road);
        //打印路径
        for (int i = 0; i < road.size(); i++) {
            Point point = road.get(i);
            System.out.println("(" + point.x + "," + point.y + ")");
        }

    }
    //第p个位置往下找节点
    private static boolean findNext(int[][] maze, List<Point> road) {
        Point point = road.get(road.size() - 1);
        if(point.x==maze.length-1&&point.y==maze[0].length-1){
            return true;
        }
        Point lastPoint = road.size()>1?road.get(road.size() - 2):null;
        Point next = null;
        //向左找 x-1
        if (point.x > 0 && (lastPoint==null||lastPoint.x != point.x - 1) &&
                maze[point.x - 1][point.y] != 1) {
            next = new Point(point.x - 1, point.y);
            // System.out.println("add(" + next.x + "," + next.y + ")");
            road.add(next);
            if (findNext(maze, road)) {
                return true;
            }
            // System.out.println("remove(" + next.x + "," + next.y + ")");
            road.remove(next);
        }
        //向右找 x+1
        if (point.x < maze.length-1 && (lastPoint==null||lastPoint.x != point.x + 1) &&
                maze[point.x + 1][point.y] != 1) {
            next = new Point(point.x + 1, point.y);
            // System.out.println("add(" + next.x + "," + next.y + ")");
            road.add(next);
            if (findNext(maze, road)) {
                return true;
            }
            // System.out.println("remove(" + next.x + "," + next.y + ")");
            road.remove(next);
        }
        //向上找 y-1
        if (point.y > 0 && (lastPoint==null||lastPoint.y != point.y - 1) &&
                maze[point.x][point.y - 1] != 1) {
            next = new Point(point.x, point.y - 1);
            // System.out.println("add(" + next.x + "," + next.y + ")");
            road.add(next);
            if (findNext(maze, road)) {
                return true;
            }
            // System.out.println("remove(" + next.x + "," + next.y + ")");
            road.remove(next);
        }
        //向下找 y+1
        if (point.y < maze[0].length-1 && (lastPoint==null||lastPoint.y != point.y + 1) &&
                maze[point.x][point.y + 1] != 1) {
            next = new Point(point.x, point.y + 1);
            // System.out.println("add(" + next.x + "," + next.y + ")");
            road.add(next);
            if (findNext(maze, road)) {
                return true;
            }
            // System.out.println("remove(" + next.x + "," + next.y + ")");
            road.remove(next);
        }
        return false;
    }
}

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