Programming Challenge -PKU- 1957 Beehives

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

1957 Beehives

問題

解答方針

六角形の格子をどう扱うかが問題.ここでは直交座標に落とすことを考える.具体的には,基準点を(0,0)としたとき,そのまわりのマスは(1,1),(0,1),(-1,0),(-1,-1),(0,-1),(1,0)となると考えればよい.

直交座標に落としてから回転を考えるのは困難なので,片方のパターンを60度ずつ回転させたものを生成してから直交座標に落とす.こうすれば,回転なしの合同判定問題に帰着できる.

回転なしで合同かどうかを判定するには,その図形を直交座標テーブル上のパターンに落として重ね合わせればよい.直交座標に落とすときは必ず左端,下端が0になるようにする.こうすれば平行移動なしの合同判定問題,つまり「完全に重なるかどうか」に帰着できる.左端,下端が0になるようにするには,一回目の走査で始点からみた左端,下端の相対座標を調べ,二回目の走査で左端,下端が0になるように始点の座標を選び,パターンを直交座標テーブルに書き込めばよい.

解答例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        for(int i=0;i<n;i++){
            String seq1 = sc.nextLine();
            String seq2 = sc.nextLine();
            sc.nextLine();
            
            Solver sol = new Solver(seq1,seq2);
            System.out.println(sol.solve());
        }
    }
}

class Solver{
    char[] seq1;
    char[] seq2;
    Solver(String seq1,String seq2){
        this.seq1 = seq1.toCharArray();
        this.seq2 = seq2.toCharArray();
    }
    public boolean solve(){
        Table t1 = new Table(seq1);
        for(int i=0;i<6;i++){
            Table t2 = new Table(seq2);
            if(t1.equals(t2)) return true;
            rotate(seq2);
        }
        return false;
    }
    

    private static void rotate(char[] seq){
        for(int i=0;i<seq.length;i++){
            seq[i]++;
            if(seq[i]>='g') seq[i]-=6;
        }
    }
}

class Table{
    int xsize;
    int ysize;
    boolean[][] egg;
    public Table(char[] seq){
        //decide parameter for initTable
        int x = 0;
        int y = 0;
        int minx = 0;
        int miny = 0;
        int maxx = 0;
        int maxy = 0;
        for(int i=0;i<seq.length;i++){
            switch(seq[i]){
            case 'a':
                x++;y++;break;
            case 'b':
                y++;break;
            case 'c':
                x--;break;
            case 'd':
                x--;y--;break;
            case 'e':
                y--;break;
            case 'f':
                x++;
            }
            if(x<minx) minx = x;
            if(y<miny) miny = y;
            if(x>maxx) maxx = x;
            if(y>maxy) maxy = y;
        }
        int xsize = maxx-minx+1;
        int ysize = maxy-miny+1;
        
        //initialize table for egg arrangement 
        initTable(ysize,xsize);
        //place eggs on egg table
        place(-miny,-minx,seq);
    }
    private void initTable(int ysize,int xsize){
        this.ysize = ysize;
        this.xsize = xsize;
        egg = new boolean[this.ysize][this.xsize];
        for(int i=0;i<this.ysize;i++){
            for(int j=0;j<this.xsize;j++){
                egg[i][j] = false;
            }
        }
    }
    private void place(int iy,int ix,char[] seq){
        egg[iy][ix] = true;
        for(int i=0;i<seq.length;i++){
            switch(seq[i]){
            case 'a':
                ix++;iy++;break;
            case 'b':
                iy++;break;
            case 'c':
                ix--;break;
            case 'd':
                ix--;iy--;break;
            case 'e':
                iy--;break;
            case 'f':
                ix++;
            }
            egg[iy][ix] = true;
        }
    }

    public boolean equals(Object o){
        Table t = (Table)o;
        if(this.ysize!=t.ysize||this.xsize!=t.xsize) return false;
        
        for(int i=0;i<this.ysize;i++){
            for(int j=0;j<this.xsize;j++){
                if(this.egg[i][j]!=t.egg[i][j]) return false;
            }
        }
        return true;
    }
}