#include #include #include #include using namespace std; const int N = 20; const int MAXQ = 10000; const int INF = 1000000000; const int SX[6] = {0, -1, -1, 0, 1, 1}; const int SY[6] = {1, 1, 0, -1, -1, 0}; int q1, q2, qx[MAXQ], qy[MAXQ], dist[2*N][2*N]; bool blocked[2*N][2*N]; int catX = 0, catY = 0; bool gameFinished, catInsideTrap; int cntLimakMove, meetX, meetY; vector > toBlock; bool inside (int row, int col) { if (abs(row) >= N || abs(col) >= N) return false; if (row <= 0) return (-N-row+1<=col && col > getCatOptions () { bfs(catX + N, catY + N); vector > result; for(int k = 0; k < 6; k++) { int px = catX + SX[k]; int py = catY + SY[k]; if (!(-N < px && px < N && -N < py && py < N) || blocked[px+N][py+N] || dist[px+N][py+N]+1 != dist[catX+N][catY+N]) continue; result.push_back(make_pair(px, py)); } return result; } void playCat () { // cerr << "Cat plays now" << endl; bfs(catX + N, catY + N); // cerr << "The distance to the end is " << dist[catX + N][catY + N] << endl; if (dist[catX+N][catY+N] == 0) { cerr << "Cat leaves the grid and he wins" << endl; while (true) ; gameFinished = true; return ; } if (dist[catX+N][catY+N] == INF) { // cerr << "The cat is trapped. Well done!" << endl; gameFinished = true; return ; } /* cerr << "Allowed directions:"; for(int k = 0; k < 6; k++) { int px = catX + SX[k]; int py = catY + SY[k]; if (!(-N < px && px < N && -N < py && py < N) || blocked[px+N][py+N] || dist[px+N][py+N]+1 != dist[catX+N][catY+N]) continue; cerr << " (" << SX[k] << ", " << SY[k] << " / " << px << ", " << py << ")"; } cerr << endl; cin >> catX >> catY;*/ vector > cc = getCatOptions(); int p = rand() % cc.size(); catX = cc[p].first; catY = cc[p].second; // cerr << catX << " " << catY << endl; } void block (int qx, int qy) { assert(inside(qx, qy)); assert(!blocked[qx+N][qy+N]); assert(qx != catX || qy != catY); blocked[qx+N][qy+N] = true; cout << "BLOCK " << qx << " " << qy << endl; } bool isNeighbor (int x1, int y1, int x2, int y2) { assert(inside(x1, y1)); assert(inside(x2, y2)); for(int k = 0; k < 6; k++) { int px = x1 + SX[k]; int py = y1 + SY[k]; if (px == x2 && py == y2) return true; } return false; } void blockFromToDoList () { pair q = toBlock[toBlock.size() - 1]; int x = q.first, y = q.second; toBlock.pop_back(); block(x, y); } int cX1, cY1, cX2, cY2; int blX, blY; void playLimak () { // cerr << "Limak plays now" << endl; ++cntLimakMove; if (cntLimakMove == 1) { block(2*catX, 2*catY); } else if (cntLimakMove == 2) { int minDist = INF; bfsFromPoint(catX+N, catY+N); int x1, y1, x2, y2; for(int i = 1; i < N+N; i++) for(int j = 1; j < N+N; j++) if (inside(i-N, j-N) && neighbors(i-N, j-N)==3 && dist[i][j] <= minDist) { if (dist[i][j] < minDist) { minDist = dist[i][j]; x1 = i-N, y1 = j-N; } else { x2 = i-N, y2 = j-N; } } int vx = (x2 - x1) / (N - 1); int vy = (y2 - y1) / (N - 1); int blX1 = x1 + vx * (N / 2); int blY1 = y1 + vy * (N / 2); int blX2 = x1 + vx * (N / 2 - 1); int blY2 = y1 + vy * (N / 2 - 1); if (dist[blX1][blY1] < dist[blX2][blY2]) { blX = blX1; blY = blY1; } else { blX = blX2; blY = blY2; } toBlock.clear(); cX1 = INF, cY1 = INF; cX2 = INF, cY2 = INF; for(int k = 0; k < 6; k++) { int px = blX + SX[k]; int py = blY + SY[k]; if (!inside(px, py)) continue; if (neighbors(px, py) == 6) { if (cX1 == INF) { cX1 = px; cY1 = py; } else { cX2 = px; cY2 = py; } } } for(int i = -N + 1; i < N; i++) for(int j = -N + 1; j < N; j++) if (inside(i, j)) { if (i == cX1 && j == cY1) continue; if (i == cX2 && j == cY2) continue; bool flag = isNeighbor(i, j, cX1, cY1) ^ isNeighbor(i, j, cX2, cY2); if (flag) { toBlock.push_back(make_pair(i, j)); } if (isNeighbor(i, j, cX1, cY1) && isNeighbor(i, j, cX2, cY2) && neighbors(i, j) == 6) { meetX = i; meetY = j; // cerr << "wait at " << meetX << " " << meetY << endl; } } // cerr << toBlock.size() << endl; blockFromToDoList(); } else if (toBlock.size() > 0) { blockFromToDoList(); } else if (!catInsideTrap && !(catX == meetX && catY == meetY)) { vector > cc = getCatOptions(); bfsFromPoint(meetX+N, meetY+N); int maxDist = -INF; int xx = 0, yy = 0; for(auto e : cc) { int x = e.first; int y = e.second; // cerr << x << " " << y << " " << dist[x+N][y+N] << endl; if (dist[x+N][y+N] > maxDist && (x != meetX || y != meetY)) { maxDist = dist[x+N][y+N]; xx = x; yy = y; } } if (xx != 0 && yy != 0) { block(xx, yy); } else { // cerr << "special case" << endl; for(int k = 0; k < 6; k++) { int px = meetX + SX[k]; int py = meetY + SY[k]; // cerr << px << " " << py; if (blocked[px+N][py+N]) { // cerr << " block" << endl; continue; } if (px == cX1 && py == cY1) { // cerr << " center1" << endl; continue; } if (px == cX2 && py == cY2) { // cerr << " center2" <> op; if (op == "WIN") { gameFinished = true; return ; } assert(op == "CAT"); cin >> catX >> catY; } void playGame () { for(int i = -N + 1; i < N; i++) for(int j = -N + 1; j < N; j++) blocked[i + N][j + N] = 0; gameFinished = false; catInsideTrap = false; catX = 0; catY = 0; cntLimakMove = 0; while (true) { playKeyboardCat(); if (!gameFinished) playLimak(); else break; } } int main(int argc, const char * argv[]) { srand(2497); int tn, maxB; cin >> tn >> maxB; while (tn--) { // cerr << "===== \n\n\n\n" << endl; playGame(); } return 0; }