题解 | #迷宫问题#

import java.util.LinkedList;
import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //右，下，上，左 0,1,2，3
    public static int dir[][] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public static char ch[] = {'R', 'D', 'U', 'L'};
    public static int m;
    public static int n;
    public static boolean vis[][];
    public static int arr[][];
    public static int xx = 0;
    public static int yy = 0;

    static class Point {
        int x, y;
        String road;

        Point(int xx, int yy, String rr) {
            this.x = xx;
            this.y = yy;
            this.road = rr;
        }
    }

    //    static void dfs(Point p) {
//        if(p.x==m-1&&p.y==n-1){
//            System.out.println("("+xx+","+yy+")");
//            for (int i = 0; i < p.road.length(); i++) {
//                char c=p.road.charAt(i);
//                if(c=='D'){
//                    xx+=1;
//                }else if (c=='U'){
//                    xx-=1;
//                } else if (c=='L') {
//                    yy-=1;
//                }else if(c=='R'){
//                    yy+=1;
//                }
//                System.out.println("("+xx+","+yy+")");
//            }
//            return;
//        }
//
//
//        for (int i = 0; i < 4; i++) {
//            int dx=p.x+dir[i][0];
//            int dy=p.y+dir[i][1];
//            if(dx>=0&&dx<m&&dy>=0&&dy<n&&!vis[dx][dy]&&arr[dx][dy]!=1){
//                Point pp = new Point(dx,dy, p.road+ ch[i]);
//                vis[dx][dy]=true;
//                dfs(pp);
//                vis[dx][dy]=false;
//            }
//        }
//    }
    static void bfs() {
        LinkedList<Point> list = new LinkedList<>();
        list.add(new Point(0, 0, ""));

        while (!list.isEmpty()) {
            Point p = list.poll();
            if (p.x == m - 1 && p.y == n - 1) {
                System.out.println("(" + xx + "," + yy + ")");
                for (int i = 0; i < p.road.length(); i++) {
                    char c = p.road.charAt(i);
                    if (c == 'D') {
                        xx += 1;
                    } else if (c == 'U') {
                        xx -= 1;
                    } else if (c == 'L') {
                        yy -= 1;
                    } else if (c == 'R') {
                        yy += 1;
                    }
                    System.out.println("(" + xx + "," + yy + ")");
                }
                return;
            }


            for (int i = 0; i < 4; i++) {
                int dx = p.x + dir[i][0];
                int dy = p.y + dir[i][1];
                if (dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] &&
                        arr[dx][dy] != 1) {
                    list.add(new Point(dx, dy, p.road + ch[i]));
                    vis[dx][dy] = true;
                }
            }
        }

    }

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

//        dfs(new Point(0, 0, ""));
        bfs();
    }
}