Programming Challenge -PKU- 2032 Square Carpets

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

2032 Square Carpets

解答方針

BFS+枝刈りが基本方針.

具体的には,使用したカーペットの枚数と床の状態(床の各マスの状態を保持した二次元配列)をまとめたクラスStateを作成し,これをデータ単位としてBFSを行う.BFSは,初期状態をキューに入れたあと,「キューから要素を取り出す->その要素から新しい要素を生成してキューに入れる」を終状態が現れるまで繰り返すことで実現できる.

問題は取り出した要素から新しい要素を生成する部分である.解答例では,取り出した要素の床のうち,傷がついているがまだカーペットで覆っていないマスを探し,そのマスを覆うようなカーペットの敷き方で可能なものをすべて生成している.

たとえば,
// 1:  scratched and not covered by carpets
// 0:  flawless
// -1: scratched but covered by carpets
0 1 1 1
1 1 1 1
1 1 1 1
から,
0 -1 -1 -1
1 -1 -1 -1
1 -1 -1 -1

0 -1 -1 1
1 -1 -1 1
1  1  1 1

0 -1 1 1
1  1 1 1
1  1 1 1
の3つの状態が生成される.

ここで,すでにキューにある床の状態と比べて「劣っている」状態はキューに入れないようにして,計算量を減らすことを考える.状態Aが状態Bに劣っているとは,「Aでカーペットで覆っているすべてのマスがBでもカーペットで覆われている」ことを指す.新しく生成された状態のカーペットの使用枚数はすでにキューにある状態のカーペットの使用枚数以上であることと合わせて考えると,キューにある状態より劣った状態を刈ることは正当な枝刈りだとわかる.

上の例では,一番上の状態以外は一番上の状態に劣っているので,枝刈りされることになる.

解答例

import java.util.*;

public class Main {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                while(true){
                        int w = sc.nextInt();
                        int h = sc.nextInt();
                        if(w==0&&h==0) break;
                        int[][] inittable = new int[h][w];
                        for(int i=0;i<h;i++){
                                for(int j=0;j<w;j++) inittable[i][j] = sc.nextInt();
                        }
                        
                        Solver sol = new Solver(w,h,inittable);
                        System.out.println(sol.solve());
                }
        }
}

class Solver{
        int w,h;
        int[][] inittable;
        Queue<State> q;
        Solver(int sw,int sh,int[][] stable){
                w = sw;
                h = sh;
                inittable = stable;
        }
        public int solve(){
                // BFS initialize
                q = new LinkedList<State>();
                State init = new State(w,h,inittable);
                q.offer(new State(w,h,inittable));
                // BFS
                while(true){
                        State st= q.poll();
                        if(st.end()){
                                return st.numc;
                        }
                        Locate criticalloc = st.criticalLocate();
                        int ca = criticalloc.a;
                        int cb = criticalloc.b;
                        for(int k=Math.max(h,w);k>0;k--){
                                for(int s=0;s<k;s++){
                                        for(int t=0;t<k;t++){
                                                // if next state is need for BFS, add it to queue
                                                addNextState(st,ca-s,ca+k-s,cb-t,cb+k-t);
                                        }
                                }
                        }
                }
        }
        private void addNextState(State st,int a1,int a2,int b1,int b2){
                if(st.coverable(a1,a2,b1,b2)){
                        State tmp = st.cover(a1,a2,b1,b2);
                        
                        //tmp is need for BFS?
                        boolean tmpneed = true;
                        if(tmp.lesser(st)) tmpneed = false;
                        else{
                                for(State state:q){
                                        if(tmp.lesser(state)){
                                                tmpneed = false;
                                                break;
                                        }
                                }
                        }
                        
                        //when tmp is need add to queue
                        if(tmpneed){
                                q.offer(tmp);
                        }
                }
        }
}

class State{
        int w,h;
        int numc;
        int[][] table;
        State(int sw,int sh,int[][] stable){
                w = sw;
                h = sh;
                numc = 0;
                table = stable;
        }
        State(State s){
                w = s.w;
                h = s.h;
                numc = s.numc;
                table = new int[h][w];
                for(int i=0;i<h;i++){
                        for(int j=0;j<w;j++) table[i][j] = s.table[i][j];
                }
        }
        public boolean end(){
                boolean ret = true;
                for(int i=0;i<h;i++){
                        for(int j=0;j<w;j++){
                                if(table[i][j]==1){
                                        ret = false;
                                }
                        }
                }
                return ret;
        }
        public Locate criticalLocate(){
                for(int i=0;i<h;i++){
                        for(int j=0;j<w;j++){
                                if(table[i][j]==1) return new Locate(i,j);
                        }
                }
                return null; // this code mustn't be executed
        }
        public boolean coverable(int a1,int a2,int b1,int b2){
                if(a1<0||a2>h||b1<0||b2>w) return false;
                
                boolean ret = true;
                for(int i=a1;i<a2;i++){
                        for(int j=b1;j<b2;j++){
                                if(table[i][j]==0){
                                        ret = false;
                                        break;
                                }
                        }
                }
                return ret;
        }
        public State cover(int a1,int a2,int b1,int b2){
                State ret = new State(this);
                for(int i=a1;i<a2;i++){
                        for(int j=b1;j<b2;j++){
                                ret.table[i][j] = -1;
                        }
                }
                ret.numc++;
                return ret;
        }
        public boolean lesser(State s){
                boolean ret = true;
                for(int i=0;i<h;i++){
                        for(int j=0;j<w;j++){
                                if(table[i][j]!=1&&s.table[i][j]==1){
                                        ret = false;
                                        break;
                                }
                        }
                }
                return ret;
        }
}

class Locate{
        int a,b;
        Locate(int pa,int pb){
                a = pa;
                b = pb;
        }
}