ICPC2012 Problem Cをやってみた。

Tweet

ICPC2012 Problem Cをやってみたよ。

http://www.cs.titech.ac.jp/icpc2012/icpc2012-mondai/icpc2012/contest/C_ja.html

サイコロを考えるのがややこしくて死にたくなった。

実行例

http://ideone.com/4In5dY

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _T_ 0 /* 天：Top */
#define _B_ 1 /* 地：Bottom */
#define _E_ 2 /* 東：East */
#define _W_ 3 /* 西：West */
#define _S_ 4 /* 南：South */
#define _N_ 5 /* 北：North */

// サイコロの値の保持
typedef struct {
 long x,y,z;
 int topside;
 int d[6];
} die_t;

// １行入力
int input(int *n, int *tn, int *fn)
{
 // 入力が 0 なら 0 を返す
 // 入力が 1文字 なら 1 を返す
 // 入力が 3文字 なら 2 を返す
 char s[4];
 char s2[4];
 int x,y;
 gets(s);
 sscanf(s,"%d",&x);
 sprintf(s2,"%d",x);
 if(strlen(s2) == strlen(s))
 {
 if(0 == x)
 {
 return 0;
 }
 else
 {
 *n = x;
 return 1;
 }
 }
 y = s[2] - '0';
 *tn = x;
 *fn = y;
 return 2;
}

// 指定座標にサイコロが存在するか確認する
int exist(long x, long y, long z, int n, die_t *dice)
{
 int i;
 for(i=0;i<n;i++)
 {
 if(
 (dice[i].x == x) &&
 (dice[i].y == y) &&
 (dice[i].z == z))
 {
 return 1;
 }
 }
 return 0;
}
int roll(die_t *dice, int i, int n)
{
 int is_roll = 0;
 int j,k,e,e2;
 long x,y,z,stop;
 int *d; // サイコロの目、d = {天,地,東,西,南,北} ※東西南北の北から見ている想定
 int _e[6]; // サイコロの目の大きい順に方向をソート
 int _x[] = {0,0,1,-1,0,0};
 int _y[] = {0,0,0,0,1,-1};

x = dice[i].x;
 y = dice[i].y;
 z = dice[i].z;
 d = dice[i].d;

stop = z; // Z=0では転がることができない！
 // 転がす
 while(stop){
 // 方角ソート
 for(j=0;j<6;j++)
 {
 for(k=0;k<6;k++)
 {
 if(d[k] == j+1)
 {
 _e[j] = k;
 }
 }
 }
 // 4～6の方向へ転がれるなら転がる。
 for(j=5;j>2;j--)
 {
 e = _e[j]; // 面の方向（0天,1地,2東,3西,4南,5北）
 if(e>1) // 3～6の面が天・地でない。
 {
 if(!exist(x+_x[e], y+_y[e], z-1, i, dice)) // 4～6の面がある方向にサイコロが無く、転がることができる場合。
 {
 // 転がる。座標処理
 x += _x[e];
 y += _y[e];
 z--;
 // 転がる。出目処理
 e2 = (e%2==0)?e+1:e-1; // eの反対面
 k = d[e];
 d[e] = d[_T_];
 d[_T_] = d[e2];
 d[e2] = d[_B_];
 d[_B_] = k;
 // 転がり探し、止め。
 j = 0;
 // 回転フラグ
 is_roll = 1;
 }
 }
 }
 stop = (0==j)? z:0; // 終了判定
 }
 dice[i].topside = d[_T_];
 dice[i].x = x;
 dice[i].y = y;
 dice[i].z = z;
 return is_roll;
}

// 上面と前面のサイコロの目から、サイコロのデータを登録する。
void setDice(die_t *die, int ti, int fi)
{
 int wi;
 int w[6][6]={ // 西方の目を天と北から得る。WEST = w[TOP][NORTH]
 {0,3,5,2,4,0},
 {4,0,1,6,0,3},
 {2,6,0,0,1,5},
 {5,1,0,0,6,2},
 {3,0,6,1,0,4},
 {0,6,2,5,3,0}
 };
 // サイコロの目の設定
 wi = w[ti-1][fi-1];
 die->d[_T_] = ti; die->d[_B_] = 7-ti;
 die->d[_N_] = fi; die->d[_S_] = 7-fi;
 die->d[_W_] = wi; die->d[_E_] = 7-wi;
}

// 主となる処理
char* main_proc(int n, int *t, int *f)
{
 int i,j;
 int ti; // 現在処理の対象としているサイコロにおけるtop,west,front(north)の目
 long x,y,z; // 座標
 int loop; // 繰り返しroll処理が必要か。
 // サイコロのデータ。
 die_t *dice;
 // 最終結果の格納変数
 char* s_res;
 int result[6] = {0,0,0,0,0,0};

 // サイコロのデータの領域割当。
 dice = (die_t *)calloc(n ,sizeof(die_t));
 // 落として転がす処理 //
 for(i=0;i<n;i++)
 {
 setDice(&dice[i], t[i], f[i]);

// 落とす。
 x = 0; y = 0; z = 0;
 while(exist(x,y,z,i,dice)) z++;
 dice[i].x = x;
 dice[i].y = y;
 dice[i].z = z;
 dice[i].topside = t[i];

// 転がす。
 loop = roll(dice, i, i);
 while(loop)
 {
 loop = 0;
 for(j=0;j<i+1;j++) loop = (roll(dice,j,i+1))?1:loop;
 }
 }
 // 表示 //
 for(i=0;i<n;i++)
 {
 x = dice[i].x;
 y = dice[i].y;
 z = dice[i].z;
 ti = dice[i].topside;
 if(!exist(x,y,z+1,n,dice)) result[ti-1]++;
 }
 // 文字列化
 s_res = (char*)calloc(255,sizeof(char));
 sprintf(s_res,"%d %d %d %d %d %d\n",result[0],result[1],result[2],result[3],result[4],result[5]);
 s_res = (char*)realloc(s_res,sizeof(char)*(strlen(s_res)+1));
 free(dice);
 return s_res;
}

int main(void)
{
 int i;
 int n, *t, *f;
 int nn, tn, fn;
 int ret;
 char *results;
 char *rtmp;
 int results_len;

 results = (char*)calloc(1,sizeof(char));

// 入力
 ret = input(&nn, &tn, &fn);
 while(ret==1)
 {
 n = nn; // 入力されるサイコロの個数
 // 入力データの領域割当
 t = (int *)calloc(n ,sizeof(int));
 f = (int *)calloc(n ,sizeof(int));
 // サイコロデータ入力
 for(i=0;i<n;i++)
 {
 if(2 != input(&nn, &tn, &fn)){
 return 1;
 }
 t[i] = tn;
 f[i] = fn;
 }
 // 主処理
 rtmp = main_proc(n, t, f);
 // 回答文字列連結
 results_len = strlen(results);
 results = (char*)realloc(results, sizeof(char)*(results_len+strlen(rtmp)+1));
 strcpy(results+results_len, rtmp);
 free(rtmp);
 // 入力データ破棄
 free(t);
 free(f);
 // 入力
 ret = input(&nn, &tn, &fn);
 }
 //最終出力
 printf("%s", results);
 free(results);
 return 0;
}