1957 Beehives

1957 Beehives

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=1957

解答方針

六角形の格子をどう扱うかが問題．ここでは直交座標に落とすことを考える．具体的には，基準点を(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;
    }
}