「2046 Gap」の編集履歴(バックアップ)一覧はこちら
「2046 Gap」(2006/04/17 (月) 02:09:02) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**2046 Gap
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2046
**解答方針
BFS.ただし同じ状態は探索しないように,一度探索した状態はHashSetに登録するようにして,登録済みの状態に達したらその時点で枝刈りするようにする.
PKUではメモリ制限が厳しいので,byte型を利用するなどしてメモリ使用量をおさえている.
**解答例
import java.util.*;
class State{
byte table[][];
int turn;
public State(byte card[][]){
int i,j,sx,sy;
table = new byte[4][8];
for(i=0;i<4;i++) table[i][0] = (byte)(10*(i+1)+1);
for(i=0;i<4;i++){
for(j=1;j<8;j++){
table[i][j] = card[i][j-1];
}
}
for(i=0;i<4;i++){
for(j=1;j<8;j++){
if(table[i][j]==11 || table[i][j]==21
|| table[i][j]==31 || table[i][j]==41)
table[i][j] = 0;
}
}
turn = 0;
}
// copy constructor
public State(State t){
table = new byte[4][8];
int i,j;
for(i=0;i<4;i++){
for(j=0;j<8;j++){
table[i][j] = t.table[i][j];
}
}
turn = t.turn;
}
public boolean canFillGap(int x,int y){
if(table[x][y] != 0) return false;
else if(table[x][y-1] == 0 || (table[x][y-1])%10 == 7) return false;
else return true;
}
public void fillGap(int x,int y){
int s,sx,sy,i,j;
sx = sy = -1;
s = table[x][y-1] + 1;
for(i=0;i<4;i++){
for(j=0;j<8;j++){
if(table[i][j] == s){
sx = i;
sy = j;
}
}
}
table[x][y] = table[sx][sy];
table[sx][sy] = 0;
turn++;
}
boolean isEnd(){
int i,j;
for(i=0;i<4;i++){
for(j=0;j<7;j++){
if(table[i][j]!=(10*(i+1)+(j+1))) return false;
}
if (table[i][7]!=0) return false;
}
return true;
}
public boolean equals(Object o){
State s = (State)o;
int i,j;
for(i=0;i<4;i++){
for(j=1;j<8;j++){
if(table[i][j]!=s.table[i][j]) return false;
}
}
return true;
}
public int hashCode(){
int value = 0;
int i,j;
for(i=0;i<4;i++){
for(j=1;j<8;j++){
value+=table[i][j];
value*=2;
}
}
return value;
}
}
class Solver{
State table;
Solver(State t){
table = new State(t);
}
int solve(){
Queue<State> q = new LinkedList<State>();
HashSet<State> h = new HashSet<State>();
//prepare for BFS
boolean end = false;
int ans = Integer.MAX_VALUE;
int i,j;
State init = new State(table);
q.offer(init);
h.add(init);
if(init.isEnd()) return 0;
//BFS
while(!q.isEmpty()&&!end){
State s = q.poll();
for(i=0;i<4;i++){
for(j=1;j<8;j++){
if(s.canFillGap(i,j)){
State temp = new State(s);
temp.fillGap(i,j);
// find answer
if(temp.isEnd()){
end = true;
ans = temp.turn;
}
// if unsearched state, add it to queue and hash
else if(!h.contains(temp)){
q.offer(temp);
h.add(temp);
}
}
}
}
}
if(ans==Integer.MAX_VALUE) ans = -1;
return ans;
}
}
public class Main{
public static void main(String args[]){
int n;
byte card[][] = new byte [4][7];
State tb;
Solver sol;
int i,j,k;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(i=0;i<n;i++){
for(j=0;j<4;j++){
for(k=0;k<7;k++){
card[j][k] = sc.nextByte();
}
}
tb = new State(card);
sol = new Solver(tb);
System.out.println(sol.solve());
}
}
}