题解 | #迷宫问题#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static List<String> minPath;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m=in.nextInt(), n = in.nextInt();
        int[][]arr=new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                arr[i][j] = in.nextInt();
            }   
        }
        List<String> cur = new ArrayList<>();
        cur.add("(0,0)");
        dfs(arr, m, n, 0, 0,cur, new HashSet<>());
        for(String str: minPath) {
            System.out.println(str);
        }
    }

    public static void dfs(int[][]arr, int m, int n, int i, int j,  List<String> curPath, Set<String> visited) {
        if(i<0||i>=m || j<0||j>=n) {
            return;
        }
        if(i == m-1 && j == n-1) {
            if(minPath == null || curPath.size()<minPath.size()) {
                minPath = new ArrayList<>(curPath);
            } 
            return;
        }
        if(i+1<=m-1 && arr[i+1][j]==0 && !visited.contains("("+(i+1)+","+j+")")) {
            String key = "("+(i+1)+","+j+")";
            visited.add(key);
            curPath.add(key);
            dfs(arr, m, n, i+1, j, curPath, visited);
            curPath.remove(curPath.size()-1);
            visited.remove(key);
        }
        if(i-1>=0 && arr[i-1][j]==0 && !visited.contains("("+(i-1)+","+j+")")) {
            String key = "("+(i-1)+","+j+")";
            visited.add(key);
            curPath.add(key);
            dfs(arr, m, n, i-1, j, curPath, visited);
            curPath.remove(curPath.size()-1);
            visited.remove(key);
        }

        if(j+1<=n-1 && arr[i][j+1]==0 && !visited.contains("("+(i)+","+(j+1)+")")) {
            String key = "("+i+","+(j+1)+")";
            visited.add(key);
            curPath.add(key);
            dfs(arr, m, n, i, j+1, curPath, visited);
            curPath.remove(curPath.size()-1);
            visited.remove(key);
        }
        if(j-1>=0 && arr[i][j-1]==0 && !visited.contains("("+(i)+","+(j-1)+")")) {
            String key = "("+i+","+(j-1)+")";
            visited.add(key);
            curPath.add(key);
            dfs(arr, m, n, i, j-1, curPath, visited);
            curPath.remove(curPath.size()-1);
            visited.remove(key);
        }
    }
}