M-Judge 10156 Kaeru Jump

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int h, w;  
10.     int[][] a;  
11.     int x0, y0;  
12.     int dir;  
13.   
14.     int[] dx={0, 1, 0, -1};  
15.     int[] dy={-1, 0, 1, 0};  
16.     char[] dc={'U', 'R', 'D', 'L'};  
17.   
18.     int nLeaf;  
19.   
20.     LinkedList<Character> solution;  
21.   
22.     void run(){  
23.         solution=new LinkedList<Character>();  
24.         h=sc.nextInt();  
25.         w=sc.nextInt();  
26.         a=new int[h][w];  
27.   
28.         for(int j=0; j<h; j++){  
29.             String s=sc.next();  
30.             for(int i=0; i<w; i++){  
31.                 char c=s.charAt(i);  
32.                 if(c=='.'){  
33.                     a[j][i]=-1;  
34.                 }else if(c=='o'){  
35.                     a[j][i]=nLeaf++;  
36.                 }else{  
37.                     a[j][i]=nLeaf++;  
38.                     x0=i;  
39.                     y0=j;  
40.                     switch(c){  
41.                     case 'U':  
42.                         dir=0;  
43.                         break;  
44.                     case 'R':  
45.                         dir=1;  
46.                         break;  
47.                     case 'D':  
48.                         dir=2;  
49.                         break;  
50.                     case 'L':  
51.                         dir=3;  
52.                         break;  
53.                     }  
54.                 }  
55.             }  
56.         }  
57.         sol();  
58.     }  
59.   
60.     void sol(){  
61.         // show();  
62.         rec(x0, y0, dir, nLeaf);  
63.         for(char c : solution)  
64.             print(c+"");  
65.         println("");  
66.     }  
67.   
68.     boolean solved=false;  
69.   
70.     void show(){  
71.         for(int j=0; j<h; j++){  
72.             for(int i=0; i<w; i++){  
73.                 print(a[j][i]+", ");  
74.             }  
75.             println("");  
76.         }  
77.         println("");  
78.     }  
79.   
80.     void rec(int x, int y, int dir0, int leaf){  
81.         if(leaf==1){  
82.             // println(Arrays.toString(solution.toArray()));  
83.             solved=true;  
84.             return;  
85.         }  
86.         // show();  
87.         int l=a[y][x];  
88.         a[y][x]=-1;  
89.         for(int d=-1; d<=1; d++){  
90.             int dir=(dir0+d+4)%4;  
91.             int i=x;  
92.             int j=y;  
93.             for(; i>=0&&i<w&&j>=0&&j<h; i+=dx[dir], j+=dy[dir]){  
94.                 if(a[j][i]>=0){  
95.                     solution.addLast(dc[dir]);  
96.                     rec(i, j, dir, leaf-1);  
97.                     if(solved)  
98.                         return;  
99.                     solution.removeLast();  
100.                     break;  
101.                 }  
102.             }  
103.         }  
104.         a[y][x]=l;  
105.     }  
106.   
107.     public static void main(String[] args){  
108.         new Main().run();  
109.     }  
110.   
111.     void println(String s){  
112.         System.out.println(s);  
113.     }  
114.   
115.     void print(String s){  
116.         System.out.print(s);  
117.     }  
118. }  

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);
    }
}