题解 | #迷宫问题#

package org.example.test.practice;

import com.alibaba.fastjson.JSONObject;

import java.util.LinkedList; import java.util.Scanner;

public class Main { static int[] x = {-1, 0, 1, 0}; static int[] y = {0, 1, 0, -1};

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNextInt()) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] nums = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nums[i][j] = scanner.nextInt();
            }
        }

// int n = 5; // int m = 5; // int[][] nums = {{0, 1, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}}; boolean[][] visit = new boolean[n][m]; LinkedList<int[]> path = new LinkedList<>(); dfs(nums, visit, path, 0, 0); } }

/**
* 采用回溯算法
*/
private static void dfs(int[][] nums, boolean[][] visit, LinkedList<int[]> path, int i, int j) {
    path.add(new int[]{i, j});
    if (i == nums.length-1 && j == nums[0].length-1) {
        for (int k = 0; k < path.size(); k++) {
            System.out.println("(" + path.get(k)[0] + "," + path.get(k)[1] + ")");
        }
        return;
    }
    visit[i][j] = true;

    for (int k = 0; k < 4; k++) {
        int a = i + x[k];
        int b = j + y[k];
        if (!(a < 0 || a >= nums.length || b < 0 || b >= nums[0].length)) {
            if (nums[a][b] != 1 && !visit[a][b]) {
                dfs(nums, visit, path, a, b);
            }
        }
    }
    path.removeLast();
    visit[i][j] = false;
}

}