题解 | #迷宫问题#

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

public class Main {
    public static void main(String[] args) {
        HJ43();
    }
    static int goal_i = 0, goal_j = 0;     //目标的坐标
    static int row = 0;
    static int column = 0;               //设置为 row * column 的表格
    static int used[][];  //用来标记地图上那些点是走过的
    static int flag = 0;           //是否能达到终点的标志
    static List<Point> path;

    /**
     * 迷宫问题
     */
    public static void HJ43() {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            row = sc.nextInt();
            column = sc.nextInt();
            int[][] graph = new int[row][column];
            goal_i = row - 1;
            goal_j = column - 1;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < column; j++) {
                    graph[i][j] = sc.nextInt();
                }
            }
            used = new int[row][column];
            // 路径存储的数组
            path = new ArrayList<>();
            DFS(graph, 0, 0);
            // 输出
            for (Point p : path) {
                System.out.println("(" + p.i + "," + p.j + ")");
            }
        }
    }

    static boolean DFS(int graph[][], int i, int j) {
        // 如果与目标坐标相同，则成功
        if (i >= 0 && i < row
                && j >= 0 && j < column
                && used[i][j] == 0
                && graph[i][j] == 0
                && flag != 1) {
            used[i][j] = 1;     //将该格子设为走过
            path.add(new Point(i,j));
            if (i == goal_i && j == goal_j) {
                flag = 1;
                return true;
            } else {
                //遍历当前格子的四个方向，如果任意一个方向能走通，则返回true
                if (DFS(graph, i + 1, j)
                        || DFS(graph, i - 1, j)
                        || DFS(graph, i, j + 1)
                        || DFS(graph, i, j - 1)
                ) {
                    return true;
                } else {
                    path.remove(path.size() - 1);
                    used[i][j] = 0;//未到终点时，需要回退的，状态回溯，将格子设置为未走过
                }
            }
        }
        return false;
    }
}

class Point {
    public int i;
    public int j;

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