#include #include using namespace std; int fact[]={1,1,2,6,24,120,720,5040}; int zakoduj(int perm[8]) { int pouz[9] = {0}; int kod = 0, i, j; for (i = 0; i < 8; i++) { for (j = 1; j < perm[i]; j++) if (!pouz[j]) { kod += fact[7-i]; } pouz[perm[i]] = 1; } return kod; } void dekoduj(int kod, int perm[8]) { int pouz[9] = {0}, i, j, k; for (i = 0; i < 8; i++) { j = kod / fact[7-i]; kod %= fact[7-i]; for (k = 1; k <= 8; k++) { if (!pouz[k]) { if (!j) break; else j--; } } pouz[k] = 1; perm[i] = k; } } int main(void) { int perm[8], cil, permn[3][8], cur, kod, i, j; int hotovo[50000] = {0}, prev[50000] = {0}; char path[50000], what[50000]; FILE *vstup = fopen("obdelnik.in", "r"), *vystup; for (i = 0; i < 8; i++) fscanf(vstup, "%d", &(perm[i])); fclose(vstup); cil=zakoduj(perm); queue q; // fronta hotovo[0] = 1; q.push(0); // 0 je v našem zápisu startovní obdélník while (!q.empty()) { cur=q.front(); q.pop(); if (cur == cil) { i = 0; while (cur) { path[++i] = what[cur]; cur = prev[cur]; } vystup = fopen("postup.out", "w"); fprintf(vystup, "%d\n", i); while (i) { fprintf(vystup, "%c", path[i]); i--; } fclose(vystup); break; } dekoduj(cur, perm); // vygeneruj tři možné transformace aktuální permutace for (i = 0; i < 4; i++) { permn[0][i] = perm[7-i]; permn[0][i+4] = perm[3-i]; permn[1][i] = perm[(i+3)%4]; permn[1][i+4] = perm[4+(i+1)%4]; } permn[2][0] = perm[0]; permn[2][1] = perm[6]; permn[2][2] = perm[1]; permn[2][3] = perm[3]; permn[2][4] = perm[4]; permn[2][5] = perm[2]; permn[2][6] = perm[5]; permn[2][7] = perm[7]; for (i = 0; i < 3; i++) { int kod = zakoduj(permn[i]); if (!hotovo[kod]) { hotovo[kod] = 1; prev[kod] = cur; switch(i) { case 0: what[kod] = 'V'; break; case 1: what[kod] = 'S'; break; case 2: what[kod] = 'R'; break; } q.push(kod); } } } return 0; }