第十届蓝桥杯大赛软件类省赛 JAVA 大学 A 组

package 迷宫;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static char[][] maze;
    static boolean[][] visit;
    static int N,M;
    public static void main(String[] args) throws FileNotFoundException {
        PrintStream ps=new PrintStream(new FileOutputStream("ans.txt"));  //文件输出
        Scanner sc = new Scanner(System.in);
        System.setOut(ps);
        N = sc.nextInt();//4
        M = sc.nextInt();//6
        sc.nextLine();
        maze = new char[M][N];
        visit = new boolean[M][N];
        String s;
        int i = 0;
        while(i < N) {
            s = sc.nextLine();
            char[] carr = s.toCharArray();
            for(int j = 0; j < carr.length; j++) {
                maze[j][i] = carr[j];
                visit[j][i] = false;
            }
            i++;
        }
        //System.out.println(X+ " " + Y + " " + check(5,3));
        node gate = bfs();
        //System.out.println(gate);
        char[] res = new char[gate.step];
        int x = gate.x;
        int y = gate.y;
        for(i = gate.step-1; i >= 0; i--) {
            node cur = gate.last;
            x = gate.x;
            y = gate.y;
            if(cur.x-x == 1) { //1,2   0,2
                res[i] = ‘L‘;    
            }else if(cur.x-x == -1) {
                res[i] = ‘R‘;
            }else if(cur.y-y == 1) {//1,2   1,1
                res[i] = ‘U‘;
            }else if(cur.y-y == -1) {
                res[i] = ‘D‘;
            }
            gate = gate.last;
        }    
        
        for(char c : res) {
            System.out.print(c);
        }
        /*for(char[] m : maze) {
            for(char n : m) {
                System.out.print(n);
            }
            System.out.println();
        }*/
        sc.close();
    }
    static int[][] dir = {{0,-1},{-1,0},{1,0},{0,1}};
    public static node bfs() {
        Queue<node> q = new LinkedList<>();
        node star = new node();
        star.x = 0;
        star.y = 0;
        visit[star.x][star.y] = true;
        q.add(star);
        while(!q.isEmpty()) {
            //System.out.println(q.peek().x + " " + q.peek().y);
            int lx = q.peek().x;
            int ly = q.peek().y;
            if(lx == M-1 && ly == N-1){
                System.out.println(q.peek().step);
                return q.peek();
            }
            for(int i = 0; i < 4; i++) {
                int x = lx + dir[i][0];
                int y = ly + dir[i][1];
                //System.out.print(" " + x + " " + y + " " + check(x,y));
                if(check(x,y) && !visit[x][y] && maze[x][y] == ‘0‘) {
                    //System.out.println("put "+x+ " " + y);
                    node tmp = new node();
                    tmp.last = q.peek();
                    tmp.x = x;
                    tmp.y = y;
                    tmp.step = q.peek().step+1;
                    visit[x][y] = true;
                    q.add(tmp);
                }
            }
            q.poll();
        }
        return null;
    }
    public static boolean check(int x, int y) {
        if(x >= 0 && x < M && y >= 0 && y < N)
            return true;
        return false;
    }
}
class node{
    node last;
    int step = 0;
    int x,y;
}