1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

private static List<int[]> path = new ArrayList<>();

    /**
     * 主方法，处理输入输出并调用回溯算法
     *
     * @param args 命令行参数
     * @throws IOException 可能抛出的IO异常
     */
    public static void main(String[] args) throws IOException {
        // 创建输入输出缓冲流
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取第一行输入，分割并转换为高度h和宽度w
        String[] strA = br.readLine().trim().split("\\s+");

        // 解析网格的高度和宽度
        int h = Integer.parseInt(strA[0]);
        int w = Integer.parseInt(strA[1]);

        // 创建网格数组和访问标记数组
        int[][] grid = new int[h][w];
        boolean[][] visited = new boolean[h][w];

        // 读取网格数据
        for (int i = 0; i < h; i++) {
            // 读取一行输入并分割
            String[] str = br.readLine().trim().split("\\s+");
            // 填充网格数据
            for (int j = 0; j < w; j++) {
                grid[i][j] = Integer.parseInt(str[j]);
            }
        }

        // 从起点(0,0)开始回溯
        backtrack(grid, h, w, 0, 0, visited);

        // 输出路径
        for (int[] pos : path) {
            out.println("(" + pos[0] + "," + pos[1] + ")");
        }

        // 刷新并关闭输出流和输入流
        out.flush();
        out.close();
        br.close();

    }

    /**
     * 使用回溯算法在网格中寻找路径
     *
     * @return 如果找到从起点到终点的路径则返回true，否则返回false
     */
    private static boolean backtrack(int[][] grid, int h, int w, int i, int j, boolean[][] visted) {
        // 检查当前位置是否有效：是否在网格范围内、是否是障碍物、是否已经访问过
        if (i < 0 || i >= h || j < 0 || j >= w || grid[i][j] == 1 || visted[i][j]) {
            return false;
        }

        // 标记当前位置为已访问，并将当前位置添加到路径中
        visted[i][j] = true;
        path.add(new int[]{i, j});

        // 如果当前位置是终点，则返回true
        if (i == h - 1 && j == w - 1) {
            return true;
        }

        // 定义四个方向：上、下、左、右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 尝试向四个方向移动
        for (int k = 0; k < 4; k++) {
            // 递归调用backtrack方法，如果找到路径则返回true
            if (backtrack(grid, h, w, i + dx[k], j + dy[k], visted)) {
                return true;
            }
        }

        // 如果四个方向都无法继续前进，则回溯：从路径中移除当前位置
        path.remove(path.size() - 1);
        return false;
    }