题解 | #迷宫问题#

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static class MyPoint{
        public int x;
        public int y;
        public MyPoint(int x, int y){
            this.x = x;
            this.y = y;
        }
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            int[][] matrix = new int[row][col];
            for (int i = 0; i < row * col; i++) {
                matrix[i / col][i % col] = scanner.nextInt();
            }

            process(matrix);
//            System.out.println();
        }
    }

    private static List<MyPoint> shortestPath = null;

    private static void process(int[][] matrix) {
        List<MyPoint> paths = new ArrayList<>();
        dfs(matrix, 0, 0, paths, 0);
        if (null != shortestPath) {
            for (MyPoint myPoint : shortestPath) {
                System.out.println("(" + myPoint.x + "," + myPoint.y + ")");
            }
            shortestPath = null;
        }
    }

    /**
     *
     * @param matrix
     * @param row
     * @param col
     * @param paths
     * @param direct 0: 本次是往右看的 前一个节点是左边
     *               1：本次是往左看的 前一个节点是右边
     *               2：本次是往上看的 前一个节点是下边
     *               3：本次是往下看的 前一个节点是上边
     */
    private static void dfs(int[][] matrix, int row, int col, List<MyPoint> paths, int direct) {
        //结束条件 到达终点
        if(matrix.length <= row || 0 > row || matrix[0].length <= col || 0 > col){
            return;
        }
        if (matrix.length == (row + 1) && matrix[0].length == (col + 1)){
            paths.add(new MyPoint(row, col));
            if (null == shortestPath || paths.size() < shortestPath.size()){
                shortestPath = new ArrayList<>(paths);
            }
            return;
        }


        //此处是墙壁 不可通行
        if (matrix[row][col] == 1){
            return;
        }

        //做选择
        paths.add(new MyPoint(row, col));

        /**
         *      * @param direct 0: 本次是往右看的 前一个节点是左边
         *      *               1：本次是往左看的 前一个节点是右边
         *      *               2：本次是往上看的 前一个节点是下边
         *      *               3：本次是往下看的 前一个节点是上边
         */
        //上次不是往左看的，可以看右边
        if (direct != 1) {
            dfs(matrix, row, col + 1, paths, 0);
        }

        //上次不是往右看的 可以看左边
        if (direct != 0) {
            dfs(matrix, row, col - 1, paths, 1);
        }

        //上次不是往下看的，可以看上边
        if (direct != 3) {
            dfs(matrix, row - 1, col, paths, 2);
        }

        //上次不是往上看的，可以看下边
        if (direct != 2) {
            dfs(matrix, row + 1, col, paths, 3);
        }

        //撤销选择
        paths.remove(paths.size() - 1);
    }
}