//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // [Tips] // XCodeでのEOF入力はCtrl+D // ¥はAlt+\ // ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////// //yukicorder //No.585 工夫のないパズル // //IDA*探索に挑戦したいが、まずは愚直に、昔8パズルでやったのを思い出して //1. なにも考えず幅優先探索BFS //結果:当然のごとくTLE・・・ // //そういえば8パズルでは双方向探索で劇的に速くなったけど・・・ //2. せっかくだから双方向BFSまた実装してみるか、復習がてら。どうせTLEになるだろうとは思いつつ //結果:それでも変わらず同じ問題でTLE・・・無駄な労力返せ〜 // //ということでようやく本題のIDA*探索へ。大いに蟻本と渦巻本を参考にしながら //3. 知識あり(ヒューリスティクスを使った) ID-DFS (Iterative Deepening Depth-First Search) である、ID-A*を実装 //結果:なんとダメでした。TLE。2のときより1問しか多く解けなかった。 //もっとフツーに攻略法ライクに解くんだってさ。これまた徒労でした。ちーん。。。 // //3-a. 構造体PUZZLEの状態をstring stateで表現していたが、これを試しにchar配列にしてみると高速化されたりしないか実験 //なんとこれだけで大幅にACが増えた!!string使ってたのバカバカバカバカバカバカ!! //86手の問題が解けて、96手の問題がTLEだったから、あとほんの少し高速化できればいけそうなんだけどなー。 // //実例: //まず以下が3.の状態でstringを使っている場合、 //FHLE //MOIC //DNPB //AKGJ //20 //R 0 2 //R 2 1 //R 3 1 //C 1 1 //R 2 1 //C 0 1 //R 3 3 //C 0 1 //R 0 3 //R 1 2 //R 2 2 //C 2 1 //R 1 1 //C 1 1 //R 2 2 //C 2 3 //R 2 1 //R 0 1 //C 2 2 //R 0 3 //numOfSearch = 318372 //0.0960 sec //Program ended with exit code: 0 // //そして以下がstateをchar配列に変えた場合であるが、めちゃめちゃ速くなった!!! 0.0960sec ===> 0.0300sec //こういう構造体を自作するケースでstring使っちゃうとめっちゃ遅くなるんやなって実感できてたいへん勉強になりました。 //FHLE //MOIC //DNPB //AKGJ //20 //R 0 2 //R 2 1 //R 3 1 //C 1 1 //R 2 1 //C 0 1 //R 3 3 //C 0 1 //R 0 3 //R 1 2 //R 2 2 //C 2 1 //R 1 1 //C 1 1 //R 2 2 //C 2 3 //R 2 1 //R 0 1 //C 2 2 //R 0 3 //numOfSearch = 318372 //0.0300 sec //Program ended with exit code: 0 // // // // //まだ意地でもad−hocのやり方やらずに、なんとか教科書解法で解こうとしている・・・ので、 //4. 知識あり(ヒューリティクスを使った) BFS (Breadth-First Search) である、A*を試しに実装してみる <== イマココ //結果:全然TLE。サンプル問題3題くらいしかACならず。やっぱり優先順位比較とかする分めちゃめちゃ遅くなるんだなあ・・・。 //ただ、先の例で見ると以下の通り、実行速度はめちゃめちゃ遅いけど、探索回数自体はめちゃめちゃ減っているという。トレードオフやなあ。 //当然のごとく、最短手数は得られなくなっている。じゃあもうA*探索ってメリットなくない?って思っちゃう。 //FHLE //MOIC //DNPB //AKGJ //18 //R 0 1 //C 0 1 //R 3 1 //C 1 1 //C 3 1 //R 2 1 //C 3 1 //C 0 2 //R 1 2 //C 2 1 //R 0 2 //C 0 1 //R 1 1 //R 2 3 //C 0 1 //C 1 1 //R 2 1 //C 1 3 //numOfSearch = 43269 //2.2190 sec //Program ended with exit code: 0 // // //ということでここまで徒労した上で、ようやく本解答に挑戦 //5. Ad-hocなこのパズルの必勝法を実装 <== イマココ // //////////////////////////////////////// //#define debug //******************************************************************************************************************************************* #ifdef debug #include #endif #include #include // next_permutation #include #include #include #include #include #include //memcpy #include #include #include #include #include //accumulate #include //#include //hash func. #include //ifstream, ofstream #include //insert_iterator::inserter #include //#define NDEBUG //If NDEBUG is defined before #include , assert will be ignored. You had better define NDEBUG when u submit the code. #include //assert using namespace std; #define dout cout //If u wanna output to a text file instead of standard output, plz define OUTPUTFILE. //#define OUTPUTFILE "output.txt" //************************************************************ #ifdef OUTPUTFILE #define dout outputfile ofstream outputfile(OUTPUTFILE); #define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt" #endif #define din cin //If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを. //#define INPUTFILE "input.txt" //************************************************************** #ifdef INPUTFILE #define din inputfile ifstream inputfile(INPUTFILE); #endif #define scand(A) scanf("%d", &(A)) #define scans(A) scanf("%s", (A)) #define printd(A) printf("%d\n", (A)) #define prints(A) printf("%s\n", (A)) #define disp(A) dout << #A << " = " << setw(3) << (A) << endl #define disP(A) dout << setw(3) << (A) << " " #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl #define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl #define line dout << "---------------\n" #define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1 #define p(i) ((i)/2) #define l(i) ((i)*2) #define r(i) ((i)*2+1) #define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16) #define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1 #define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0 int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; typedef pair ii; typedef pair iii; typedef vector vi; typedef long long ll; typedef unsigned long long ull; //const int INF = (1LL<<31)-1; const int NONE = -1; //const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow. //const ull INF_ULL = (ull)1e19-1ULL; //#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん #define N_MAX 100010 //num of vertex or element //#define M_MAX 124760 //num of edge //#define DATA_MAX 1010 #define N 4 #define N2 16 char GOAL[N2+1] = "ABCDEFGHIJKLMNOP"; //24 patterns of possible move #define K_MAX 24 char dir[K_MAX] = {'R','R','R','R','R','R','R','R','R','R','R','R','C','C','C','C','C','C','C','C','C','C','C','C'}; //direction int pos[K_MAX] = { 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 }; //position int dif[K_MAX] = { 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 }; //difference int target_i; int target_j; #define round(i) (((i)%N+N)%N) //0, 1, ... , N-1に変換する (負の数も含めて) struct PUZZLE { char state[N2+1]; vi path; //初期状態からここまでの手 int cost; //初期状態からここまでの手数、pathに保存されている手の数に等しい bool isGoal() { return not strcmp(this->state, GOAL); } void display() { #ifdef debug dout << "----\n"; disp(this->state); show(path,0,this->cost); disp(this->cost); rep(i,0,N) { rep(j,0,N) { dout << (i==target_i and j== target_j ? "*" : " ") << this->state[i*N+j] << " "; } dout << endl; } dout << endl; #endif } void rotate(int k) { //pをk番目 (k=0...23) の動かし方で1手動かして返す //同時に、cost、pathも更新する #ifdef debug dout << "--- rotate( " << k << " )\n"; disp(dir[k]); disp(pos[k]); disp(dif[k]); #endif path.push_back(k); this->cost++; int start, last, jump; char tmp[N2]; if(dir[k]=='R') { jump = 1; start = N * pos[k]; last = start + (N-1)*jump; // = start + 3 } else { assert(dir[k]=='C'); jump = N; start = pos[k]; last = start + (N-1)*jump; // = start + 12 } //一旦tmpにdifだけずらしてコピーしておいて for(int i=start; i<=last; i+=jump) { int next = i + dif[k] * jump; if(next > last) next = i - (N - dif[k])*jump; tmp[next] = state[i]; } //元の配列を更新する for(int i=start; i<=last; i+=jump) { state[i] = tmp[i]; } } void rotRowToRight(int pos, int dif) { int dir = 0; rotate( dir*N*(N-1) + pos*(N-1) + dif-1 ); } void rotColumnToDown(int pos, int dif) { int dir = 1; rotate( dir*N*(N-1) + pos*(N-1) + dif-1 ); } void swap2AdjacentElementsInTheSameRow(int row, int j1, int j2) { #ifdef debug dout << "---- swap( row=" << row << ", " << j1 << ", " << j2 <<" )\n"; #endif assert(0<=row and rowj2) swap(j1, j2); int column = round(j1 - 1); assert(column!=j2); #ifdef debug disp(row); disp(j1); disp(j2); disp(column); #endif rotColumnToDown(column, 1); display(); rotRowToRight(row, 3); display(); rotColumnToDown(column, 3); display(); rotRowToRight(row, 2); display(); rotColumnToDown(column, 1); display(); rotRowToRight(row, 3); display(); rotColumnToDown(column, 3); display(); rotRowToRight(row, 3); display(); } } puzzle; void init() { } void display() { #ifdef debug dout << "----\n"; #endif } void solve() { #ifdef debug dout << "======================== solve()\n"; puzzle.display(); #endif int sorted_i = -1; //sorted_i行目の int sorted_j = -1; //sorted_j番目のマスまでが揃えられている int goal_i; int goal_j; //最下行を犠牲にして、それ以外のマスを揃える rep(i,0,N*(N-1)) { //i(targetChar)を揃える (i=0:A, i=1:B, ..., i=11:L) //注意:この時点で、i-1まではすでに揃えられている状態 // その事実はsorted_i, sorted_jで表現することにする char targetChar = i + 'A'; int targetPos = NONE; //find targetChar rep(j,0,N2) { if( puzzle.state[j] == targetChar ) { targetPos = j; } } assert(targetPos!=NONE); target_i = targetPos/N; target_j = targetPos%N; goal_i = i/N; goal_j = i%N; //#ifdef debug // dout << "Step 0\n"; // dout << "すでに対象が正しい位置に配置されている場合は、continue\n"; //#endif if( target_i == goal_i and target_j == goal_j ) { continue; } #ifdef debug dout << "------------------------------\n"; disp(i); disp(targetChar); disp(targetPos); disp(target_i); disp(target_j); disp(goal_i); disp(goal_j); disp(sorted_i); puzzle.display(); #endif #ifdef debug dout << "Step 1\n"; dout << "対象がフリーの行になければ、対象をフリーの行まで下げる\n"; #endif if( target_i <= sorted_i ) { puzzle.rotColumnToDown(target_j, 1); target_i++; assert(target_i goal_i); puzzle.rotColumnToDown(goal_j, target_i - goal_i); puzzle.display(); } #ifdef debug dout << "Step 4\n"; dout << "goalマスと対象の列が違ったら、goalマスと同じ列に横にずらす\n"; #endif if( target_j != goal_j ) { puzzle.rotRowToRight(target_i, round(goal_j-target_j)); target_j = goal_j; puzzle.display(); } #ifdef debug dout << "Step 5 (Step 3の逆手順)\n"; dout << "goalマスと対象の行が違ったら、goalマスの位置まで上げる\n"; #endif if( goal_i != target_i ) { puzzle.rotColumnToDown(target_j, round(goal_i-target_i)); target_i = goal_i; puzzle.display(); } sorted_j++; if(sorted_j==N) { sorted_i++; sorted_j=0; } } #ifdef debug dout << "Step M\n"; dout << "最下行の最左の要素 (M) が揃っていなければ、それを1手で揃える\n"; #endif goal_i = N-1; goal_j = 0; char targetChar = goal_i*N + goal_j + 'A'; target_i = N-1; target_j = NONE; rep(j,0,N) { if(puzzle.state[target_i*N + j] == targetChar) { target_j = j; break; } } assert(target_j!=NONE); if(goal_j!=target_j) { puzzle.rotRowToRight(target_i, round(goal_j-target_j)); target_i = goal_i; target_j = goal_j; puzzle.display(); } #ifdef debug dout << "Step FINAL\n"; dout << "残り(N-1)要素を、ネットで見つけた「隣接する2マスを交換する手順」を使って、揃える\n"; #endif goal_i = N-1; goal_j = 1; targetChar = goal_i*N + goal_j + 'A'; target_i = N-1; target_j = NONE; rep(j,0,N) { if(puzzle.state[target_i*N + j] == targetChar) { target_j = j; break; } } assert(target_j!=NONE); #ifdef debug disp(goal_j); disp(target_j); #endif if(goal_j!=target_j) { //1文字目が揃っていない #ifdef debug dout << "Nが揃っていない\n"; #endif if(target_j==2) { //今注目している文字 (1文字目に配置するべき文字) の位置が2 #ifdef debug dout << "Nが2の位置にあるので、1,2をswapする\n"; #endif puzzle.swap2AdjacentElementsInTheSameRow(target_i, 1, 2); } else { //今注目している文字 (1文字目に配置するべき文字) の位置が3 assert(target_j==3); #ifdef debug dout << "Nが3の位置にあるので、2,3をswap後、1,2をswap\n"; #endif puzzle.swap2AdjacentElementsInTheSameRow(target_i, 2, 3); puzzle.swap2AdjacentElementsInTheSameRow(target_i, 1, 2); } //1文字目が揃った!! } #ifdef debug dout << "Nまで揃った\n"; #endif //2文字目をチェック target_j = 2; targetChar = target_i*N + target_j + 'A'; if(puzzle.state[target_i*N + target_j]==targetChar) { //2文字目も揃っている、それすなわち3文字目も揃っている、つまり全部揃っている return; } else { //2文字目と3文字目が揃っていないのでswap puzzle.swap2AdjacentElementsInTheSameRow(target_i, target_j, round(target_j+1)); } #ifdef debug dout << "すべて揃った\n"; #endif assert(puzzle.isGoal()); } int main() { //cin, coutの高速化 *注意:cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように! cin.tie(0); //cinとcoutの同期を切る ios::sync_with_stdio(false); //iostreamとstdioの同期を切る //read input data // scand(N); string s; char ss[N2+1]; rep(i,0,N) { din >> s; rep(j,0,N) { ss[i*N+j] = s[j]; } } ss[N2] = '\0'; //------------------------------------------------------------------------------------------ #ifdef debug //start timer auto startTime = chrono::system_clock::now(); #endif //------------------------------------------------------------------------------------------ strcpy(puzzle.state, ss); init(); display(); solve(); #ifdef debug dout << "=== OUTPUT ===\n"; #endif if( puzzle.cost!=NONE ) { dout << puzzle.cost << endl; rep(i,0,puzzle.cost) { dout << dir[puzzle.path[i]] << " " << pos[puzzle.path[i]] << " " << dif[puzzle.path[i]] << endl; } } else { dout << "UNSOLVABLE!!!\n"; } //------------------------------------------------------------------------------------------ #ifdef debug //stop timer auto endTime = chrono::system_clock::now(); auto dur = endTime - startTime; auto msec = chrono::duration_cast(dur).count(); dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n"; #endif //------------------------------------------------------------------------------------------ #ifdef INPUTFILE inputfile.close(); #endif #ifdef OUTPUTFILE outputfile.close(); cout << "\"" << OutputFilePath << "\"" << endl; #endif return 0; }