Hypyt

#include <bits/stdc++.h>
using namespace std;
typedef vector<bitset<55>> VK;
typedef vector<bitset<101>> VS;
typedef vector<pair<int, int>> VA;

bool oob(int x, int y, int n, int m) {
  return x < 0 || y < 0 || x >= n || y >= m;
}

bool hau(int x, int y, int n, int m, VS &siirtyma, VK &kautu, VA &A, int ps,
         int rem) {
  if (rem == 0)
    return true;
  vector<pair<int, int>> W;
  int mx = ps - 1;
  for (auto i :
       {x - mx, x - mx - 1, x + mx, x + mx + 1, x - mx - 2, x + mx + 2}) {
    if (i < 0 || i >= n)
      continue;
    int ofx = abs(i - x);
    for (int j = 0; j < m; j++) {
      int ofy = abs(j - y);
      if (kautu[i][j])
        continue;
      if (siirtyma[i - x + 50][j - y + 50])
        continue;
      int lk = max(ofx, ofy);
      if (lk > mx) {
        W.clear();
        mx = lk;
      }
      if (lk == mx && W.size() < 2)
        W.push_back({i, j});
    }
  }
  for (int i = 0; i < n; i++) {
    int ofx = abs(i - x);
    for (auto j :
         {y - mx, y - mx - 1, y + mx, y + mx + 1, y + mx + 2, y - mx - 2}) {
      if (j < 0 || j >= m)
        continue;
      int ofy = abs(j - y);
      if (kautu[i][j])
        continue;
      if (siirtyma[i - x + 50][j - y + 50])
        continue;
      int lk = max(ofx, ofy);
      if (lk > mx) {
        W.clear();
        mx = lk;
      }
      if (lk == mx && W.size() < 2)
        W.push_back({i, j});
    }
  }
  ps = mx;
  for (auto &u : W) {
    int i = u.first;
    int j = u.second;
    siirtyma[i - x + 50][j - y + 50] = 1;
    kautu[i][j] = 1;
    if (hau(i, j, n, m, siirtyma, kautu, A, ps, rem - 1)) {
      A.push_back({i - x, j - y});
      return true;
    }
    kautu[i][j] = 0;
    siirtyma[i - x + 50][j - y + 50] = 0;
  }
  return false;
}

void solve(int n, int m) {
  VS siirtyma(101);
  VK kautu(55);
  VA a;
  kautu[0][0] = 1;
  if (!hau(0, 0, n, m, siirtyma, kautu, a, max(n, m), n * m - 1)) {
    cout << "QAQ" << endl;
    exit(1);
  }
  reverse(a.begin(), a.end());
  for (auto u : a)
    cout << u.first << " " << u.second << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    solve(n, m);
  }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: ACCEPTED

Test 5

Group: 2

Verdict: ACCEPTED