Aizu Online Judge 1218 Push!!

■1218 Push!!

人の座標と荷物の座標を状態とし，距離を荷物を押した回数としたダイクストラで解ける．

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 mx0, my0, cx0, cy0, gx, gy;  
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.      if(a[j][i]==2){  
32.       cx0=i;  
33.       cy0=j;  
34.       a[j][i]=0;  
35.      }else if(a[j][i]==3){  
36.       gx=i;  
37.       gy=j;  
38.       a[j][i]=0;  
39.      }else if(a[j][i]==4){  
40.       mx0=i;  
41.       my0=j;  
42.       a[j][i]=0;  
43.      }  
44.     }  
45.    }  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   PriorityQueue<P> que=new PriorityQueue<P>();  
52.   boolean[][][][] visited=new boolean[m][n][m][n];  
53.   int[][][][] d=new int[m][n][m][n];  
54.   
55.   for(int k=0; k<m; k++){  
56.    for(int j=0; j<n; j++){  
57.     for(int i=0; i<m; i++){  
58.      fill(d[k][j][i], INF);  
59.     }  
60.    }  
61.   }  
62.   
63.   que.add(new P(mx0, my0, cx0, cy0));  
64.   visited[mx0][my0][cx0][cy0]=true;  
65.   d[mx0][my0][cx0][cy0]=0;  
66.   
67.   int[] dx={0, 0, -1, 1};  
68.   int[] dy={1, -1, 0, 0};  
69.   
70.   for(; !que.isEmpty();){  
71.    P p=que.poll();  
72.    if(d[p.mx][p.my][p.cx][p.cy]<p.d){  
73.     continue;  
74.    }  
75.    for(int i=0; i<4; i++){  
76.     P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);  
77.     int push=0;  
78.     // 人が画面外or移動不可  
79.     if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){  
80.      continue;  
81.     }  
82.     // 人の移動先がブロック  
83.     if(q.mx==q.cx&&q.my==q.cy){  
84.      q.cx+=dx[i];  
85.      q.cy+=dy[i];  
86.      push=1;  
87.     }  
88.     // ブロックが画面外or配置不可  
89.     if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){  
90.      continue;  
91.     }  
92.     // 訪問していない  
93.     if(!visited[q.mx][q.my][q.cx][q.cy]){  
94.      q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]  
95.        +push;  
96.      visited[q.mx][q.my][q.cx][q.cy]=true;  
97.      que.offer(q);  
98.     }  
99.    }  
100.   }  
101.   
102.   int min=INF;  
103.   for(int j=0; j<n; j++){  
104.    for(int i=0; i<m; i++){  
105.     min=min(min, d[i][j][gx][gy]);  
106.    }  
107.   }  
108.   
109.   println(""+(min==INF?-1:min));  
110.   
111.  }  
112.   
113.  class P implements Comparable<P>{  
114.   int mx, my, cx, cy;  
115.   int d;  
116.   
117.   P(int mx, int my, int cx, int cy){  
118.    this.mx=mx;  
119.    this.my=my;  
120.    this.cx=cx;  
121.    this.cy=cy;  
122.   }  
123.   
124.   @Override  
125.   public int compareTo(P p){  
126.    return d-p.d;  
127.   }  
128.  }  
129.   
130.  void debug(Object... os){  
131.   System.err.println(Arrays.deepToString(os));  
132.  }  
133.   
134.  void print(String s){  
135.   System.out.print(s);  
136.  }  
137.   
138.  void println(String s){  
139.   System.out.println(s);  
140.  }  
141.   
142.  public static void main(String[] args){  
143.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
144.   new Main().run();  
145.  }  
146. }  

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 mx0, my0, cx0, cy0, gx, gy;

 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();
     if(a[j][i]==2){
      cx0=i;
      cy0=j;
      a[j][i]=0;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=0;
     }else if(a[j][i]==4){
      mx0=i;
      my0=j;
      a[j][i]=0;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  PriorityQueue<P> que=new PriorityQueue<P>();
  boolean[][][][] visited=new boolean[m][n][m][n];
  int[][][][] d=new int[m][n][m][n];

  for(int k=0; k<m; k++){
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     fill(d[k][j][i], INF);
    }
   }
  }

  que.add(new P(mx0, my0, cx0, cy0));
  visited[mx0][my0][cx0][cy0]=true;
  d[mx0][my0][cx0][cy0]=0;

  int[] dx={0, 0, -1, 1};
  int[] dy={1, -1, 0, 0};

  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.mx][p.my][p.cx][p.cy]<p.d){
    continue;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);
    int push=0;
    // 人が画面外or移動不可
    if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){
     continue;
    }
    // 人の移動先がブロック
    if(q.mx==q.cx&&q.my==q.cy){
     q.cx+=dx[i];
     q.cy+=dy[i];
     push=1;
    }
    // ブロックが画面外or配置不可
    if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){
     continue;
    }
    // 訪問していない
    if(!visited[q.mx][q.my][q.cx][q.cy]){
     q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]
       +push;
     visited[q.mx][q.my][q.cx][q.cy]=true;
     que.offer(q);
    }
   }
  }

  int min=INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    min=min(min, d[i][j][gx][gy]);
   }
  }

  println(""+(min==INF?-1:min));

 }

 class P implements Comparable<P>{
  int mx, my, cx, cy;
  int d;

  P(int mx, int my, int cx, int cy){
   this.mx=mx;
   this.my=my;
   this.cx=cx;
   this.cy=cy;
  }

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