Aizu Online Judge 0121 Seven Puzzle

■0121 Seven Puzzle

先に，全てのパターンについて最小ステップ数を計算しておく．BFSで可能．

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.  HashMap<Integer, Integer> map;  
17.  int[] a;  
18.  int w=4, h=2;  
19.   
20.  void run(){  
21.   a=new int[w*h];  
22.   init();  
23.   for(; sc.hasNext();){  
24.    for(int i=0; i<w*h; i++){  
25.     a[i]=sc.nextInt();  
26.    }  
27.    println(""+map.get(id(a)));  
28.   }  
29.  }  
30.   
31.  void init(){  
32.   
33.   LinkedList<S> que=new LinkedList<S>();  
34.   map=new HashMap<Integer, Integer>();  
35.   
36.   que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));  
37.   map.put(id(que.peek().a), 0);  
38.   int[] dx={0, 0, -1, 1};  
39.   int[] dy={-1, 1, 0, 0};  
40.   
41.   for(; !que.isEmpty();){  
42.    S s=que.poll();  
43.    int p=s.y*w+s.x;  
44.    for(int i=0; i<4; i++){  
45.     int x2=s.x+dx[i];  
46.     int y2=s.y+dy[i];  
47.     int p2=y2*w+x2;  
48.     if(x2>=0&&x2<w&&y2>=0&&y2<h){  
49.      int[] a2=s.a.clone();  
50.      int t=a2[p];  
51.      a2[p]=a2[p2];  
52.      a2[p2]=t;  
53.      S s2=new S(x2, y2, a2);  
54.      if(!map.containsKey(id(s2.a))){  
55.       que.offer(s2);  
56.       map.put(id(s2.a), map.get(id(s.a))+1);  
57.      }  
58.     }  
59.    }  
60.   }  
61.  }  
62.   
63.  int id(int[] a){  
64.   int res=0;  
65.   for(int e : a){  
66.    res=res*10+e;  
67.   }  
68.   return res;  
69.  }  
70.   
71.  class S{  
72.   int x, y;  
73.   int[] a;  
74.   
75.   S(int x, int y, int[] a){  
76.    this.x=x;  
77.    this.y=y;  
78.    this.a=a;  
79.   }  
80.  }  
81.   
82.  void debug(Object... os){  
83.   System.err.println(Arrays.deepToString(os));  
84.  }  
85.   
86.  void print(String s){  
87.   System.out.print(s);  
88.  }  
89.   
90.  void println(String s){  
91.   System.out.println(s);  
92.  }  
93.   
94.  public static void main(String[] args){  
95.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
96.   new Main().run();  
97.  }  
98. }  

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;

 HashMap<Integer, Integer> map;
 int[] a;
 int w=4, h=2;

 void run(){
  a=new int[w*h];
  init();
  for(; sc.hasNext();){
   for(int i=0; i<w*h; i++){
    a[i]=sc.nextInt();
   }
   println(""+map.get(id(a)));
  }
 }

 void init(){

  LinkedList<S> que=new LinkedList<S>();
  map=new HashMap<Integer, Integer>();

  que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
  map.put(id(que.peek().a), 0);
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   S s=que.poll();
   int p=s.y*w+s.x;
   for(int i=0; i<4; i++){
    int x2=s.x+dx[i];
    int y2=s.y+dy[i];
    int p2=y2*w+x2;
    if(x2>=0&&x2<w&&y2>=0&&y2<h){
     int[] a2=s.a.clone();
     int t=a2[p];
     a2[p]=a2[p2];
     a2[p2]=t;
     S s2=new S(x2, y2, a2);
     if(!map.containsKey(id(s2.a))){
      que.offer(s2);
      map.put(id(s2.a), map.get(id(s.a))+1);
     }
    }
   }
  }
 }

 int id(int[] a){
  int res=0;
  for(int e : a){
   res=res*10+e;
  }
  return res;
 }

 class S{
  int x, y;
  int[] a;

  S(int x, int y, int[] a){
   this.x=x;
   this.y=y;
   this.a=a;
  }
 }

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