Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int m, n;  
17.  int[][] a;  
18.  int[] c;  
19.   
20.  void run(){  
21.   for(;;){  
22.    m=sc.nextInt();  
23.    n=sc.nextInt();  
24.    if((m|n)==0){  
25.     break;  
26.    }  
27.    a=new int[n][m];  
28.    for(int j=0; j<n; j++){  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=sc.nextInt();  
31.     }  
32.    }  
33.    c=new int[4];  
34.    for(int i=0; i<4; i++){  
35.     c[i]=sc.nextInt();  
36.    }  
37.    solve();  
38.   }  
39.  }  
40.   
41.  void solve(){  
42.   int[][][] d=new int[n][m][4];  
43.   for(int j=0; j<n; j++){  
44.    for(int i=0; i<m; i++){  
45.     fill(d[j][i], INF);  
46.    }  
47.   }  
48.   int[] dx={1, 0, -1, 0};  
49.   int[] dy={0, 1, 0, -1};  
50.   PriorityQueue<P> que=new PriorityQueue<P>();  
51.   que.offer(new P(0, 0, 0));  
52.   d[0][0][0]=0;  
53.   for(; !que.isEmpty();){  
54.    P p=que.poll();  
55.    if(p.d>d[p.y][p.x][p.v]){  
56.     continue;  
57.    }  
58.    int[] cost=c.clone();  
59.    if(a[p.y][p.x]!=4){  
60.     cost[a[p.y][p.x]]=0;  
61.    }  
62.    for(int i=0; i<4; i++){  
63.     P q=new P(p.x, p.y, (p.v+i)%4);  
64.     q.x+=dx[q.v];  
65.     q.y+=dy[q.v];  
66.     if(q.x<0||q.x>=m||q.y<0||q.y>=n){  
67.      continue;  
68.     }  
69.     if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){  
70.      q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];  
71.      que.offer(q);  
72.     }  
73.    }  
74.   }  
75.   int ans=INF;  
76.   for(int i=0; i<4; i++){  
77.    ans=min(ans, d[n-1][m-1][i]);  
78.   }  
79.   println(ans+"");  
80.  }  
81.   
82.  class P implements Comparable<P>{  
83.   int x, y, v;  
84.   int d;  
85.   
86.   P(int x, int y, int v){  
87.    this.x=x;  
88.    this.y=y;  
89.    this.v=v;  
90.   }  
91.   
92.   @Override  
93.   public int compareTo(P p){  
94.    return d-p.d;  
95.   }  
96.  }  
97.   
98.  void debug(Object... os){  
99.   System.err.println(Arrays.deepToString(os));  
100.  }  
101.   
102.  void print(String s){  
103.   System.out.print(s);  
104.  }  
105.   
106.  void println(String s){  
107.   System.out.println(s);  
108.  }  
109.   
110.  public static void main(String[] args){  
111.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
112.   new Main().run();  
113.  }  
114. }  

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

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, n;
 int[][] a;
 int[] c;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   c=new int[4];
   for(int i=0; i<4; i++){
    c[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[][][] d=new int[n][m][4];
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }
  int[] dx={1, 0, -1, 0};
  int[] dy={0, 1, 0, -1};
  PriorityQueue<P> que=new PriorityQueue<P>();
  que.offer(new P(0, 0, 0));
  d[0][0][0]=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(p.d>d[p.y][p.x][p.v]){
    continue;
   }
   int[] cost=c.clone();
   if(a[p.y][p.x]!=4){
    cost[a[p.y][p.x]]=0;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.x, p.y, (p.v+i)%4);
    q.x+=dx[q.v];
    q.y+=dy[q.v];
    if(q.x<0||q.x>=m||q.y<0||q.y>=n){
     continue;
    }
    if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){
     q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];
     que.offer(q);
    }
   }
  }
  int ans=INF;
  for(int i=0; i<4; i++){
   ans=min(ans, d[n-1][m-1][i]);
  }
  println(ans+"");
 }

 class P implements Comparable<P>{
  int x, y, v;
  int d;

  P(int x, int y, int v){
   this.x=x;
   this.y=y;
   this.v=v;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}