M-Judge 10156 Kaeru Jump

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem B: Kaeru Jump
より

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int h, w;
    int[][] a;
    int x0, y0;
    int dir;

    int[] dx={0, 1, 0, -1};
    int[] dy={-1, 0, 1, 0};
    char[] dc={'U', 'R', 'D', 'L'};

    int nLeaf;

    LinkedList<Character> solution;

    void run(){
        solution=new LinkedList<Character>();
        h=sc.nextInt();
        w=sc.nextInt();
        a=new int[h][w];

        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                char c=s.charAt(i);
                if(c=='.'){
                    a[j][i]=-1;
                }else if(c=='o'){
                    a[j][i]=nLeaf++;
                }else{
                    a[j][i]=nLeaf++;
                    x0=i;
                    y0=j;
                    switch(c){
                    case 'U':
                        dir=0;
                        break;
                    case 'R':
                        dir=1;
                        break;
                    case 'D':
                        dir=2;
                        break;
                    case 'L':
                        dir=3;
                        break;
                    }
                }
            }
        }
        sol();
    }

    void sol(){
        // show();
        rec(x0, y0, dir, nLeaf);
        for(char c : solution)
            print(c+"");
        println("");
    }

    boolean solved=false;

    void show(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+", ");
            }
            println("");
        }
        println("");
    }

    void rec(int x, int y, int dir0, int leaf){
        if(leaf==1){
            // println(Arrays.toString(solution.toArray()));
            solved=true;
            return;
        }
        // show();
        int l=a[y][x];
        a[y][x]=-1;
        for(int d=-1; d<=1; d++){
            int dir=(dir0+d+4)%4;
            int i=x;
            int j=y;
            for(; i>=0&&i<w&&j>=0&&j<h; i+=dx[dir], j+=dy[dir]){
                if(a[j][i]>=0){
                    solution.addLast(dc[dir]);
                    rec(i, j, dir, leaf-1);
                    if(solved)
                        return;
                    solution.removeLast();
                    break;
                }
            }
        }
        a[y][x]=l;
    }

    public static void main(String[] args){
        new Main().run();
    }

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }
}