grid.cpp

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using namespace __gnu_cxx;

typedef unsigned long long ullong;
typedef long long llong;
typedef list<int> EdgeList;
typedef vector<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj, v, it) \
  for (EdgeList::iterator it = adj[v].begin(); it != adj[v].end(); ++it)
#define FOR(v, it) for (auto it = v.begin(); it != v.end(); ++it)

int mat[32][32];
int r, c;
int main() {
  int n_cases;
  cin >> n_cases;
  for (int ctr = 0; ctr < n_cases; ++ctr) {
    cin >> r >> c;
    if (r == 2 && c <= 4 || r == 3 && c <= 3) {
      printf("Case #%d: IMPOSSIBLE\n", ctr + 1);
      continue;
    }
    memset(mat, 0, sizeof(mat));
    vector<int> rowv;
    vector<int> colv;
    for (int y = 0; y < r; ++y) {
      rowv.push_back(y);
    }
    for (int x = 0; x < c; ++x) {
      colv.push_back(x);
    }

    bool good = false;
    const int steps = 1 << 10;
    int lower = 1;
    int px = c / 2;
    int py = r / 2;
    mat[py][px] = 1;
    for (int step = 2; step < steps; ++step) {
      random_shuffle(rowv.begin(), rowv.end());
      random_shuffle(colv.begin(), colv.end());
      for (; lower <= step; ++lower) {
        bool found = false;
        for (int y : rowv) {
          if (y == py) {
            continue;
          }
          for (int x : colv) {
            if (x == px || x + y == px + py || x - y == px - py) continue;
            if (mat[y][x] >= lower) continue;
            mat[y][x] = step;
            py = y;
            px = x;
            found = true;
            break;
          }
          if (found) {
            break;
          }
        }
        if (found) break;
      }
#ifdef DEBUG
      printf("STEP %d\n", step);
      for (int y = 0; y < r; ++y) {
        for (int x = 0; x < c; ++x) {
          printf("%4d ", mat[y][x]);
        }
        printf("\n");
      }
      fflush(stdout);
      cout.flush();
#endif
      if (mat[py][px] != step) break;
      if (step - lower + 1 == r * c) {
        good = true;
        break;
      }
    }
#ifdef DEBUG
    printf("finale\n");
    for (int y = 0; y < r; ++y) {
      for (int x = 0; x < c; ++x) {
        printf("%4d ", mat[y][x]);
      }
      printf("\n");
    }
#endif

    if (good) {
      printf("Case #%d: POSSIBLE\n", ctr + 1);
      vector<tuple<int, int, int>> ans;
      ans.reserve(r * c);
      for (int y = 0; y < r; ++y) {
        for (int x = 0; x < c; ++x) {
          ans.emplace_back(mat[y][x], x, y);
        }
      }
      sort(ans.begin(), ans.end());
      for (auto p : ans) {
        int d, x, y;
        tie(d, x, y) = p;
        printf("%d %d\n", y + 1, x + 1);
      }
    } else {
      printf("Case #%d: IMPOSSIBLE\n", ctr + 1);
    }
  }
  return 0;
}