https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0300?year=2014
考察過程
1. 操作がやばいので、操作の実装以外はそんなに難しくないのでは?
2. よく見ると最大8回で揃うようなので、操作は7回まで見ればいい(7回操作してできなかったら8回が答え)
3. 毎回4通りの操作があるので、4^7だが、これは余裕
4. BFSをすればいいのだが、遷移がやばいので頑張る
5. c++なら状態はvector
解法
https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0300/judge/3156503/C++14
実装が厳しいので頑張る。
check(v) := 全面揃っているか確認する
回転はswapを使うと、5回のswapで実現できる。
何をswapするかで添え字を入れておこう。
添字を2次元配列で管理しておけば、ループで4通りの操作を実現できる。
int N; //--------------------------------------------------------------------------------------------------- int check(vector<int> &v) { rep(i, 0, 9) if (v[0] != v[i]) return 0; rep(i, 9, 12) if (v[9] != v[i]) return 0; rep(i, 12, 15) if (v[12] != v[i]) return 0; rep(i, 15, 18) if (v[15] != v[i]) return 0; rep(i, 18, 21) if (v[18] != v[i]) return 0; rep(i, 21, 30) if (v[21] != v[i]) return 0; return 1; } pair<int, int> E[4][5] = { {{7,22},{8,23} ,{9,24} ,{18,13} ,{10,12} } ,{ {3 , 22},{ 6, 25} ,{ 9, 28} ,{ 12, 19} ,{13 ,15 } } ,{ {1 , 24},{ 4,27 } ,{7 ,30 } ,{ 10,21 } ,{16 , 18} } ,{ {1 ,28 },{2 ,29 } ,{3 , 30} ,{21 ,19 } ,{15 ,16 } } }; //--------------------------------------------------------------------------------------------------- int solve() { vector<int> v; rep(i, 0, 30) { int p; cin >> p; v.push_back(p); } set<vector<int>> done; if (check(v)) return 0; queue<vector<int>> que; done.insert(v); que.push(v); rep(i, 1, 8) { queue<vector<int>> que2; while (!que.empty()) { vector<int> q = que.front(); que.pop(); rep(j, 0, 4) { vector<int> qq = q; rep(k, 0, 5) swap(qq[E[j][k].first - 1], qq[E[j][k].second - 1]); if (done.count(qq)) continue; if (check(qq)) return i; que2.push(qq); done.insert(qq); } } swap(que, que2); } return 8; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(_, 0, N) cout << solve() << endl; }