블 루 브리지 컵알고리즘 증가학 패 의 미로.

문제 묘사 학 패 는 모두의 숙제 를 빼 앗 아 갔 고 반장 은 학생 들 이 숙제 를 되 찾 는 것 을 돕 기 위해 학 패 를 찾 아가 결 투 를 하기 로 했다.그러나 학 패 는 다른 사람 이 방해 하지 않 기 위해 한 성에 살 고 있 습 니 다. 성 밖 은 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.Scanner;

/** * @author   * */
public class Main {
    private static int n;
    private static int m;
    private static char[][] mat;
    private static String minResult;
    private static boolean[][] hasReach; 

    /** * @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];
        hasReach=new boolean[n][m];
        for(int i=0;i<n;i++){
            mat[i]=sc.next().toCharArray();
        }
        hasReach[0][0]=true;
        fun("",0,0,'U');
        fun("",0,0,'D');
        fun("",0,0,'R');
        fun("",0,0,'L');
// hasReach[0][0]=false;

        System.out.println(minResult.length());
        System.out.println(minResult);
    }


    private static void fun(String result,int i,int j,char direction){
        if(i==n-1&&j==m-1){
            if(minResult==null||minResult.length()>result.length()||(minResult.length()==result.length()&&minResult.compareTo(result)>0)){
                minResult=result;
            }
            return;
        }

        int nextI=i;
        int nextJ=j;
        switch (direction) {
        case 'U': {
            nextI--;
            if (judge(nextI, nextJ)) {
                hasReach[nextI][nextJ]=true;
                fun(result+'U', nextI, nextJ, 'U');
                fun(result+'U', nextI, nextJ, 'D');
                fun(result+'U', nextI, nextJ, 'R');
                fun(result+'U', nextI, nextJ, 'L');
                hasReach[nextI][nextJ]=false;
            }
            break;
        }
        case 'D': {
            nextI++;
            if (judge(nextI, nextJ)) {
                hasReach[nextI][nextJ]=true;
                fun(result+'D', nextI, nextJ, 'U');
                fun(result+'D', nextI, nextJ, 'D');
                fun(result+'D', nextI, nextJ, 'R');
                fun(result+'D', nextI, nextJ, 'L');
                hasReach[nextI][nextJ]=false;

            }
            break;
        }

        case 'R': {
            nextJ++;
            if (judge(nextI, nextJ)) {
                hasReach[nextI][nextJ]=true;
                fun(result+'R', nextI, nextJ, 'U');
                fun(result+'R', nextI, nextJ, 'D');
                fun(result+'R', nextI, nextJ, 'R');
                fun(result+'R', nextI, nextJ, 'L');
                hasReach[nextI][nextJ]=false;
            }
            break;
        }
        case 'L': {
            nextJ--;
            if (judge(nextI, nextJ)) {
                hasReach[nextI][nextJ]=true;
                fun(result+'L', nextI, nextJ, 'U');
                fun(result+'L', nextI, nextJ, 'D');
                fun(result+'L', nextI, nextJ, 'R');
                fun(result+'L', nextI, nextJ, 'L');
                hasReach[nextI][nextJ]=false;
            }
            break;
        }
        }

    }

    private static boolean judge(int nextI,int nextJ){
        if(nextI==-1||nextI==n||nextJ==-1||nextJ==m){
            return false;
        }else if(hasReach[nextI][nextJ]==true){
            return false;
        }else if(mat[nextI][nextJ]=='1'){
            return false;
        }else{
            return true;
        }
    }
}