ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1181 Biased Dice

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp


・概要
サイコロを転がしたりする問題です。
この問題ではサイコロの面に関する情報が2面しか与えられないことに注意が必要です。
説明が難しいので各自問題文を読んでください。


・解法
サイコロのシミュレーション問題です。

サイコロのライブラリを持っている人はすぐ解けてしまうのかなーなど思いつつも、私はライブラリを持っていなかったので一から実装しました。

概要にも書いた通り、サイコロに関する情報は2面しか与えられないので、入力時に残り1面を求めなければいけません。
求め方についてですが、問題文にサイコロの絵が載っているので、それをもとに求めることができます。
サイコロに関する基礎知識として、サイコロのある面とその対称にある面の目の合計7になります。 これ重要です。

あとは問題文の指示にしたがって、サイコロを回転させたりして最後にそれぞれの目が何個見えるかをカウントすればよいです。

ちなみに入力は100以下なので、配列の大きさを200x200くらいとっておいてサイコロを落とす場所を(100,100)にすればよいと思います。


ソースコード

#include<iostream>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)

static const int dx[]={0,1,0,-1};
static const int dy[]={1,0,-1,0};
//right→front→left→back

struct Dice{
   int front, top, right;
   Dice(){}
   Dice(int f, int t, int r):front(f),top(t),right(r){}
};

int n;
int canSee[200][200], height[200][200], ans[7];
int dicePos[7][7];//dicePos[top][front] = right
Dice dice[100];

void init(){
   memset(dicePos,0,sizeof(dicePos));
   dicePos[1][2] = 3; dicePos[1][3] = 5; dicePos[1][5] = 4; dicePos[1][4] = 2;
   dicePos[2][1] = 4; dicePos[2][4] = 6; dicePos[2][6] = 3; dicePos[2][3] = 1;
   dicePos[3][1] = 2; dicePos[3][2] = 6; dicePos[3][6] = 5; dicePos[3][5] = 1;
   dicePos[4][1] = 5; dicePos[4][5] = 6; dicePos[4][6] = 2; dicePos[4][2] = 1;
   dicePos[5][1] = 3; dicePos[5][3] = 6; dicePos[5][6] = 4; dicePos[5][4] = 1;
   dicePos[6][2] = 4; dicePos[6][4] = 5; dicePos[6][5] = 3; dicePos[6][3] = 2;
}

void input(){
   int t,f;
   for(int i = 0 ; i < n ; i++){
      cin >> t >> f;
      dice[i] = Dice(f, t, dicePos[t][f]);
   }      
}

void solve(){
   memset(canSee,0,sizeof(canSee));
   memset(height,0,sizeof(height));
   memset(ans,0,sizeof(ans));   

   for(int i = 0 ; i < n ; i++){
      int x = 100, y = 100;

      if(canSee[x][y]==0){
	 canSee[x][y] = dice[i].top;
	 height[x][y] = 1;
      }
      else{
	 while(true){
	    int dir = -1, val = 3;
	    rep(k,4){
	       int nx = x + dx[k];
	       int ny = y + dy[k];
	       if(height[x][y] > height[nx][ny]){
		  if(k==0){//right
		     if(dice[i].right > val){
			dir = 0;
			val = dice[i].right;
		     }
		  }
		  if(k==1){//front
		     if(dice[i].front > val){
			dir = 1;
			val = dice[i].front;
		     }
		  }
		  if(k==2){//left
		     if(7 - dice[i].right > val){
			dir = 2;
			val = 7 - dice[i].right;
		     }
		  }
		  if(k==3){//back
		     if(7 - dice[i].front > val){
			dir = 3;
			val = 7 - dice[i].front;
		     }
		  }
	       }
	    }
	    
	    if(dir==-1){
	       canSee[x][y] = dice[i].top;
	       height[x][y]++;
	       break;
	    }
	    else{
	       x += dx[dir];
	       y += dy[dir];
	       if(dir==0)dice[i] = Dice(dice[i].front, 7-dice[i].right, dice[i].top);//right
	       if(dir==1)dice[i] = Dice(dice[i].top, 7-dice[i].front, dice[i].right);//front
	       if(dir==2)dice[i] = Dice(dice[i].front, dice[i].right, 7-dice[i].top);//left
	       if(dir==3)dice[i] = Dice(7-dice[i].top, dice[i].front, dice[i].right);//back
	    }
	 }
      }
   }

   //count
   for(int i = 0 ; i < 200 ; i++){
      for(int j = 0 ; j < 200 ; j++){
	 ans[canSee[i][j]]++;
      }
   }
   
   //output
   for(int i = 1 ; i <= 6 ; i++){
      if(i==6)cout << ans[i] << endl;
      else cout << ans[i] << " ";
   }
}

int main(){
   init();
   while(cin >> n){
      if(n==0)break;
      input();
      solve();
   }
   return 0;
}