题解 | #迷宫问题#

BFS + 栈返回结果

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int c = sc.nextInt();
        int[][] nums = new int[r][c];
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j ++){
                nums[i][j] = sc.nextInt();
            }
        }
        
        bfs(nums,0,0,r,c);
    }
    public static void bfs(int[][] nums,int i,int j,int r,int c){
        Queue<int[]> re = new LinkedList<>();
        Deque<int[]> path = new LinkedList<>();
        Deque<int[]> res = new LinkedList<>();
        int distance = 0;
        re.add(new int[] { i, j, distance});
        while(!re.isEmpty()){
            int[] cur = re.poll();
            i = cur[0]; j = cur[1]; distance = cur[2];
            if(!(i < 0 || i >= r || j < 0 || j > c -1 || nums[i][j] == 1)){
                nums[i][j] = 1;
                path.push(new int[] { i, j, distance});
                if(i == r - 1 && j == c - 1){
                    while(!path.isEmpty()){
                        int[] temp = path.pop();
                        if(distance == temp[2] && i - temp[0] <= 1 && i - temp[0] >= -1 && j - temp[1]  <= 1 && j - temp[1] >= -1){
                            res.push(new int[] {temp[0], temp[1]});
                            i = temp[0]; j = temp[1];
                            distance--;
                        }
                    }
                    while(!res.isEmpty()){
                        int[] temp = res.pop();
                        System.out.println("(" + temp[0] + "," + temp[1] + ")");
                    }
                return;
            }
                re.add(new int[] { i + 1, j, distance + 1});
                re.add(new int[] { i - 1, j, distance + 1});
                re.add(new int[] { i, j + 1, distance + 1});
                re.add(new int[] { i, j - 1, distance + 1});
        }
        }
    }
}