//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // [Tips] // XCodeでのEOF入力はCtrl+D // ¥はAlt+\ // ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////// //yukicorder //No.585 工夫のないパズル //IDA*探索に挑戦したいが、まずは愚直に //1. なにも考えず幅優先探索BFS // //////////////////////////////////////// //#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 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 ll INF_LL = (ll)9e18-1LL; //Be careful for overflow. const ull INF_ULL = (ull)1e19-1ULL; const int NONE = -1; const ll MOD = (ll)1e9+7; //大きい素数の代表といえばこの人、10億7さん const int N_MAX = 3010; //num of vertex or element const int M_MAX = 124760; //num of edge const int DATA_MAX = 1010; int N = 4; int N2 = N*N; string GOAL = "ABCDEFGHIJKLMNOP"; //24 patterns of possible move const int 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 ans = 0; struct PUZZLE { string state; string path; bool operator < (const PUZZLE &p) const { rep(i,0,N2) { if(state[i]==p.state[i]) continue; else return this->state[i] < p.state[i]; } return false; //completely equal } bool isGoal() { return this->state==GOAL; } void display() { dout << "----\n"; disp(this->state); disp(this->path); rep(i,0,N) { rep(j,0,N) { dout << this->state[i*N+j]; } dout << endl; } dout << endl; } static PUZZLE rotate(PUZZLE p, int k) { //pをk番目 (k=0...23) の動かし方で1手動かして返す 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] = p.state[i]; } //元の配列を更新する for(int i=start; i<=last; i+=jump) { p.state[i] = tmp[i]; } return p; } }; void init() { } void display() { #ifdef debug dout << "----\n"; #endif } string solve_BFS(PUZZLE p) { queue Q; map alreadySearched; Q.push(p); alreadySearched[p] = true; PUZZLE x, y; while(not Q.empty()) { x = Q.front(); Q.pop(); #ifdef debug dout << "=====================\n"; x.display(); #endif if(x.isGoal()) { #ifdef debug dout << "x is GOAAAAAAAAAAAAAAAAAAAL!!\n"; #endif return x.path; } //xから1手で遷移できる状態yをすべて羅列する rep(k,0,K_MAX) { y = x.rotate(x, k); #ifdef debug dout << "---\n"; disp(k); y.display(); #endif if(not alreadySearched[y]) { alreadySearched[y] = true; y.path += dir[k]; y.path += to_string(pos[k]); y.path += to_string(dif[k]); Q.push(y); #ifdef debug dout << "since y has not been searched yet, add into Q.\n"; disp(y.path); #endif } } } return "UNSOLVABLE"; } 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, initialState; rep(i,0,N) { din >> s; initialState += s; } PUZZLE puzzle; puzzle.state = initialState; puzzle.path = ""; init(); display(); //------------------------------------------------------------------------------------------ #ifdef debug //start timer auto startTime = chrono::system_clock::now(); #endif //------------------------------------------------------------------------------------------ string sol = solve_BFS(puzzle); #ifdef debug dout << "=== OUTPUT ===\n"; #endif dout << sol.size()/3 << endl; rep(i,0,sol.size()) { dout << sol[i] << (i%3==2? "\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; }