Aizu Online Judge 1214 Walking Ant

■1214 Walking Ant

BFSで解ける．但し状態を，(x, y, hp)とする．hpは現在の体力を表す．

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 sx, sy, gx, gy;  
18.  int[][] a;  
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.       sx=i;  
33.       sy=j;  
34.       a[j][i]=1;  
35.      }else if(a[j][i]==3){  
36.       gx=i;  
37.       gy=j;  
38.       a[j][i]=1;  
39.      }  
40.     }  
41.    }  
42.    solve();  
43.   }  
44.  }  
45.   
46.  void solve(){  
47.   int max=7;  
48.   int[][][] d=new int[n][m][max];  
49.   boolean[][][] visited=new boolean[n][m][max];  
50.   LinkedList<P> que=new LinkedList<P>();  
51.   
52.   for(int j=0; j<n; j++){  
53.    for(int i=0; i<m; i++){  
54.     fill(d[j][i], INF);  
55.    }  
56.   }  
57.   
58.   que.offer(new P(sx, sy, 6));  
59.   d[sy][sx][6]=0;  
60.   visited[sy][sx][6]=true;  
61.   
62.   int[] dx={0, 0, -1, 1};  
63.   int[] dy={-1, 1, 0, 0};  
64.   
65.   for(; !que.isEmpty();){  
66.    P p=que.poll();  
67.    for(int i=0; i<4; i++){  
68.     P q=new P(p.x+dx[i], p.y+dy[i], p.hp-1);  
69.     if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){  
70.      if(a[q.y][q.x]==4){  
71.       q.hp=6;  
72.      }  
73.      if(!visited[q.y][q.x][q.hp]){  
74.       que.offer(q);  
75.       d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;  
76.       visited[q.y][q.x][q.hp]=true;  
77.      }  
78.     }  
79.    }  
80.   }  
81.   int ans=INF;  
82.   for(int k=0; k<max; k++){  
83.    ans=min(ans, d[gy][gx][k]);  
84.   }  
85.   println((ans!=INF?ans:-1)+"");  
86.  }  
87.   
88.  class P{  
89.   int x, y, hp;  
90.   
91.   P(int x, int y, int hp){  
92.    this.x=x;  
93.    this.y=y;  
94.    this.hp=hp;  
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 sx, sy, gx, gy;
 int[][] a;

 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){
      sx=i;
      sy=j;
      a[j][i]=1;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=1;
     }
    }
   }
   solve();
  }
 }

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

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

  que.offer(new P(sx, sy, 6));
  d[sy][sx][6]=0;
  visited[sy][sx][6]=true;

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

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i], p.hp-1);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){
     if(a[q.y][q.x]==4){
      q.hp=6;
     }
     if(!visited[q.y][q.x][q.hp]){
      que.offer(q);
      d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;
      visited[q.y][q.x][q.hp]=true;
     }
    }
   }
  }
  int ans=INF;
  for(int k=0; k<max; k++){
   ans=min(ans, d[gy][gx][k]);
  }
  println((ans!=INF?ans:-1)+"");
 }

 class P{
  int x, y, hp;

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

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