http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1181&lang=jp
ものを回転させる問題は他にも
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2169
がありますが、置換で回転をあらわす時の注意事項。
例えば、
(0, 1, 2, 3, 4, 5)
(4, 0, 2, 3, 5, 1)
だとしたら、位置0にあった要素を4に移す置換と考えます。つまり、
f={4, 0, 2, 3, 5, 1}、
変換前の値をvとすれば、変換後のv'は
v'[f[i]]=v[i]を満たします。
値iがjに変わるような置換としがちですが、これではうまく行きません。場所を移すと考えましょう。
set<vi> S; map<vi, vector<vi>> M; int F[4][6] = { //1, 2, 3, 4の方向に転がる {1, 5, 2, 3, 0, 4}, //a {2, 1, 5, 0, 4, 3}, //b {3, 1, 0, 5, 4, 2}, //ib {4, 0, 2, 3, 5, 1} //ia }; int dx[5] = {0, 1, 0, 0, -1}; int dy[5] = {0, 0, 1, -1, 0}; void solve() { queue<vi> que; que.push(vi{0, 1, 2, 3, 4, 5}); S.insert(vi{0, 1, 2, 3, 4, 5}); while(!que.empty()) { vi vec = que.front(); que.pop(); rep(i, 0, 4) { vi tmp(6); rep(j, 0, 6) { tmp[F[i][j]] = vec[j]; } if(!S.count(tmp)) { S.insert(tmp); que.push(tmp); } } } for(auto vec : S) { rep(i, 0, 4) { vi tmp(6); rep(j, 0, 6) { tmp[F[i][j]] = vec[j]; } M[vec].pb(tmp); } // debug(vec, vector<vi>(all(M[vec]))); } while(true) { int N; cin >> N; if(N == 0) break; map<vi, int> D; while(N--) { int a, b; cin >> a >> b; a--; b--; vi dice; for(auto vec : S) { if(vec[0] == a && vec[1] == b) dice = vec; } vi d({100, 0, 0}); while(true) { if(d[0] == 0) break; d[0]--; if(D.count(d)) { d[0]++; pi p(-1, -1); //num and dir for(int i = 1; i <= 4; i++) { vi tmp = d; tmp[0]--; tmp[1] += dx[i]; tmp[2] += dy[i]; if(!D.count(tmp) && dice[i] >= 3) { MAX(p, pi(dice[i], i)); } } if(p.fst == -1) break; else { d[1] += dx[p.sec]; d[2] += dy[p.sec]; dice = M[dice][p.sec - 1]; } } } // debug(d, dice[0]); D[d] = dice[0]; } vi ans(6, 0); for(pair<vi, int> d : D) { d.fst[0]++; if(!D.count(d.fst)) ans[d.sec]++; } rep(i, 0, 6) { cout << ans[i] << (i == 5 ? '\n' : ' '); } } }
面倒of面倒
