POJ 2697 - A Board Game
http://poj.org/problem?id=2697
概要
\(4 \times 4\) のボード上に4個の白石と4つの黒石がある。 初期状態の盤面と最終状態の盤面が与えられるので、白石から交互に石を移動させて初期状態から最終状態にするまで最小で何ターンかかるか答える。 移動は上下左右斜めの8方向にすることができ、ボードの端か別の石にあたるまで移動させる。
制約
特になし
解法
BFS。白石同士・黒石同士の区別は無いので、状態数は白石の場所の選び方 \(\begin{eqnarray}{}_{16}\mathrm{C}_{4}\end{eqnarray}\) と黒石の場所の選び方 \(\begin{eqnarray}{}_{12}\mathrm{C}_{4}\end{eqnarray}\) で900900通りしかない。 よって、がんばって盤面をエンコード・デコードすれば十分 BFS できる。
poj/2697.cc1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 using namespace std; 5 6 struct quadruple { int a[4]; }; 7 quadruple tbl1[1820], tbl2[495]; 8 int rev_tbl1[16][16][16][16], rev_tbl2[16][16][16][16]; 9 struct grid 10 { 11 char a[4][5]; 12 void dump() { 13 for (int i = 0; i < 4; i++) { 14 puts(a[i]); 15 } 16 } 17 }; 18 19 int encode(const grid& g) 20 { 21 int ws[4], bs[4]; 22 int w = 0, b = 0; 23 for (int i = 0; i < 4; i++) { 24 for (int j = 0; j < 4; j++) { 25 if (g.a[i][j] == 'w') { 26 ws[w++] = i*4+j; 27 } else if (g.a[i][j] == 'b') { 28 bs[b++] = i*4+j - w; 29 } 30 } 31 } 32 return rev_tbl1[ws[0]][ws[1]][ws[2]][ws[3]] * 495 + rev_tbl2[bs[0]][bs[1]][bs[2]][bs[3]]; 33 } 34 35 void decode(grid &g, int n) 36 { 37 const quadruple ws = tbl1[n/495], bs = tbl2[n%495]; 38 int w = 0, b = 0; 39 for (int i = 0; i < 4; i++) { 40 for (int j = 0; j < 4; j++) { 41 if (ws.a[w] == 4*i+j) { 42 ++w; 43 g.a[i][j] = 'w'; 44 } else if (bs.a[b]+w == 4*i+j) { 45 ++b; 46 g.a[i][j] = 'b'; 47 } else { 48 g.a[i][j] = '*'; 49 } 50 } 51 g.a[i][4] = '\0'; 52 } 53 } 54 55 void init(quadruple *t, int r[16][16][16][16], int N) 56 { 57 int c = 0; 58 for (int i = 0; i < N; i++) { 59 for (int j = i+1; j < N; j++) { 60 for (int k = j+1; k < N; k++) { 61 for (int l = k+1; l < N; l++) { 62 t[c].a[0] = i; 63 t[c].a[1] = j; 64 t[c].a[2] = k; 65 t[c].a[3] = l; 66 r[i][j][k][l] = c; 67 ++c; 68 } 69 } 70 } 71 } 72 } 73 74 int main() 75 { 76 init(tbl1, rev_tbl1, 16); 77 init(tbl2, rev_tbl2, 12); 78 79 int T; 80 scanf("%d", &T); 81 while (T-- > 0) { 82 grid start, goal; 83 for (int i = 0; i < 4; i++) { 84 scanf("%s", start.a[i]); 85 } 86 for (int i = 0; i < 4; i++) { 87 scanf("%s", goal.a[i]); 88 } 89 const int e_goal = encode(goal); 90 static const int SIZE = 900900; 91 static int dist[SIZE]; 92 static const int INF = 100000000; 93 fill_n(dist, SIZE, INF); 94 queue<int> q; 95 q.push(encode(start)); 96 dist[q.front()] = 0; 97 while (!q.empty()) { 98 const int n = q.front(); 99 q.pop(); 100 if (n == e_goal) { 101 printf("%d\n", dist[n]); 102 goto NEXT; 103 } 104 105 grid g; 106 decode(g, n); 107 for (int i = 0; i < 4; i++) { 108 for (int j = 0; j < 4; j++) { 109 static char wb[] = {'w', 'b'}; 110 if (g.a[i][j] != wb[dist[n]&1]) { 111 continue; 112 } 113 for (int a = 0; a < 8; a++) { 114 static const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1}; 115 static const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1}; 116 int k = i, l = j; 117 while (true) { 118 const int x = k + di[a]; 119 const int y = l + dj[a]; 120 if (0 <= x && x < 4 && 0 <= y && y < 4 && g.a[x][y] == '*') { 121 // ok 122 } else { 123 break; 124 } 125 if (a % 2 == 1) { 126 // diag 127 if (g.a[k][y] != '*' || g.a[x][l] != '*') { 128 break; 129 } 130 } 131 k = x; 132 l = y; 133 } 134 swap(g.a[k][l], g.a[i][j]); 135 const int e = encode(g); 136 if (dist[n]+1 < dist[e]) { 137 dist[e] = dist[n]+1; 138 q.push(e); 139 } 140 swap(g.a[k][l], g.a[i][j]); 141 } 142 } 143 } 144 } 145 puts("-1"); 146 NEXT: 147 ; 148 } 149 return 0; 150 }