블 루 브리지 컵알고리즘 증가학 패 의 미로 (BFS 방법)

문제 묘사 학 패 는 모두의 숙제 를 빼 앗 아 갔 고 반장 은 학생 들 이 숙제 를 되 찾 는 것 을 돕 기 위해 학 패 를 찾 아가 결 투 를 하기 로 했다.그러나 학 패 는 다른 사람 이 방해 하지 않 기 위해 한 성에 살 고 있 습 니 다. 성 밖 은 2 차원 의 격자 미로 입 니 다. 성에 들 어 가 려 면 반드시 미 로 를 통과 해 야 합 니 다.반장 과 여동생 이 함께 있어 야 하기 때문에 칼 을 가 는 것 은 장작 을 베 는 일 을 그 르 치지 않 는 다. 그 는 시간 을 절약 하기 위해 선인 에 게 서 미궁의 지 도 를 구 해 최 단 노선 을 미리 계산 하려 고 한다.그러나 그 는 지금 여동생 에 게 이 일 을 설명 하고 있 기 때문에 너 에 게 그 에 게 가장 짧 은 노선 을 찾 아 달라 고 부탁 했다.형식 첫 줄 의 정수 n, m 를 입력 하 십시오. 미궁의 길이 입 니 다.다음 n 줄, 각 줄 의 m 개 수, 수 사이 에 간격 이 없 으 며 0 또는 1 중의 하나 입 니 다.0 은 이 칸 이 통과 할 수 있다 는 것 을 나타 내 고, 1 은 안 된다 는 것 을 나타 낸다.만약 당신 이 지금 미궁 좌표 (1, 1) 에 있 는 곳, 즉 왼쪽 상단, 미궁 의 출구 가 (n, m) 에 있다 고 가정 하 세 요.이동 할 때마다 상하 좌우 4 개 방향 으로 만 통과 할 수 있 는 다른 칸 으로 이동 할 수 있 으 며, 이동 할 때마다 한 걸음 으로 계산한다.데이터 보증 (1, 1), (n, m) 통과 가능.출력 형식 첫 줄 의 한 수 는 필요 한 최소 걸음 수 K 입 니 다.두 번 째 줄 의 K 문 자 는 각각 위, 아래 를 나타 내 는 8712 ° {U, D, L, R} 입 니 다.길이 가 같은 최 단 경로 가 여러 개 있 으 면 이 표시 방법 에서 사전 순서 가 가장 작은 것 을 선택 하 십시오.샘플 입력 입력 입력 샘플 1: 3 001 100 110
입력 샘플 2: 3 3000 000 000 샘플 출력 샘플 1: 4 RDRD
Output Sample 2: 4 DDRR 데이터 규모 와 약 정 된 20% 의 데이터 만족: 1 < = n, m < = 10 은 50% 의 데이터 만족: 1 < = n, m < = 50 은 100% 의 데이터 만족: 1 < = n, m < = 500.

import java.util.ArrayDeque;
import java.util.Scanner;
public class Main {
    private static int n;
    private static int m;
    private static char[][] mat;
    private static ArrayDeque<Node> queue=new ArrayDeque<Node>();
    private static boolean[][] hasVisited;
    private static String minSteps;
    private static  int minStepCount=Integer.MAX_VALUE;
    private static boolean isFinished=false;
    private static char[] direction={'U','D','R','L'};
    private static int[][] dir=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};

    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        mat=new char[n][m];
        hasVisited=new boolean[n][m];
        for(int i=0;i<n;i++){
            mat[i]=sc.next().toCharArray();
        }

        bfs();

        System.out.println(minStepCount);
        System.out.println(minSteps);


    }

    private static void bfs(){
        queue.offer(new Node(0,0,"",0));
        while(!queue.isEmpty()){
            Node node=queue.poll();
            hasVisited[node.x][node.y]=true;
            if(node.x==n-1&&node.y==m-1){
                isFinished=true;            
                if(minStepCount>node.stepCount){
                    minStepCount=node.stepCount;
                    minSteps=node.steps;
                }else if(minStepCount==node.stepCount&&minSteps.compareTo(node.steps)>0){
                    minSteps=node.steps;
                }
                continue;
            }

            if(isFinished){
                if(node.stepCount>=minStepCount){
                    continue;
                }
            }

            for(int i=0;i<4;i++){
                Node newNode=new Node(node.x+dir[i][0],node.y+dir[i][1],node.steps+direction[i],node.stepCount+1);
                if(check(newNode)){
                    queue.offer(newNode);
                }
            }

        }
    }
    private static boolean check(Node node){
        if(node.x==-1||node.y==-1||node.x==n||node.y==m){
            return false;
        }else if(hasVisited[node.x][node.y]){
            return false;
        }else if(mat[node.x][node.y]=='1'){
            return false;
        }else{
            return true;
        }
    }
}

class Node{
    int x;
    int y;
    String steps;
    int stepCount;
    public Node(int x,int y,String steps,int stepCount){
        this.x=x;
        this.y=y;
        this.steps=steps;
        this.stepCount=stepCount;
    }
}