// SP2003 Problem Grids. // // (inputfile as command-line argument) // #include #include #include #include #include #include #include using namespace std; typedef vector Tile; string probname; int numtiles; vector Tiles(80); Tile Target(16); int bestCnt; vector BestStack(11); vector CurStack(11); vector used(10); int tries=0; void readtile(istream &in1, Tile &tile) { char ch; for (int i=0; i<16; i++) { in1 >> ch; tile[i]=ch; } } void rotate(const Tile &t1, Tile &t2) { char sq[4][4]; int i, j, k; for( k = 0, i = 0; i <= 3; i++) for( j = 0; j <= 3; j++) { sq[i][j] = t1[k]; k = k + 1; } for( k = 0, j = 0; j <= 3; j++) for( i = 3; i >= 0; i--) { t2[k] = sq[i][j]; k = k + 1; } } void flip(const Tile &t1, Tile &t2) { char sq[4][4]; int i, j, k; for( k = 0, i = 0; i <= 3; i++) for( j = 0; j <= 3; j++) { sq[i][j] = t1[k]; k = k + 1; } for( k = 0, i = 3; i >= 0; i--) for( j = 0; j <= 3; j++) { t2[k] = sq[i][j]; k = k + 1; } } bool equal(const Tile &T1, const Tile &T2) { for (int i=0; i<16; i++) if (T1[i]!=T2[i]) return false; return true; } void search(const Tile &Image, vector &CurStack, int curCnt) { if (tries > 200000) return; else tries++; // cheating if (curCnt >= bestCnt) return; #ifdef debug cerr << "curCnt=" << curCnt << ':'; for (int h=0; h> probname >> numtiles; if (probname[0]=='#') return 0; cout << probname; assert((numtiles >= 1) && (numtiles <= 10)); int t; for (t = 0; t <= numtiles-1; t++) { int t8 = t*8; readtile(in1,Tiles[t8]); rotate(Tiles[t8+0], Tiles[t8+1]); rotate(Tiles[t8+1], Tiles[t8+2]); rotate(Tiles[t8+2], Tiles[t8+3]); rotate(Tiles[t8+3], Tiles[t8+4]); flip (Tiles[t8+4], Tiles[t8+4]); rotate(Tiles[t8+4], Tiles[t8+5]); rotate(Tiles[t8+5], Tiles[t8+6]); rotate(Tiles[t8+6], Tiles[t8+7]); } readtile(in1,Target); // Now search for answer bestCnt=11; fill(used.begin(),used.end(),false); Tile curImg(16); fill(curImg.begin(),curImg.end(),'.'); vector curStack(numtiles); tries=0; search(curImg, curStack, 0); if (bestCnt==11) { cout << " noway" << endl; continue; } for (i=0; i