1957 Beehives

「1957 Beehives」の編集履歴（バックアップ）一覧はこちら

「1957 Beehives」(2006/04/17 (月) 01:51:54) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**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;
     }
 }