Ruudukko

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 0xffff
#endif

int g[12][12];
int N, M;

bool ir(int y, int x) {
  return 0 <= y && y < N && 0 <= x && x < M;
}

bool nz(int y, int x) {
  return g[y][x] != 0;
}

bool ok() {
  for (int y = 0; y < N; y++) {
    for (int x = 0; x < M; x++) {
      for (int dy = -1; dy <= 1; dy++) {
        for (int dx = -1; dx <= 1; dx++) {
          if (abs(dy) + abs(dx) != 1) continue;
          int ty = y + dy;
          int tx = x + dx;
          if (ir(ty, tx) && nz(ty, tx) && abs(g[y][x] - g[ty][tx]) == 1) {
            return false;
          }
        }
      }
    }
  }
  return true;
}



bool brute(int y, int x, int fr) {
  if (fr == N * M) {
    return ok();
  }

  for (int dy = -1; dy <= 1; dy++) {
    for (int dx = -1; dx <= 1; dx++) {
      if (abs(dy) + abs(dx) != 1) continue;
      int ty = y + dy;
      int tx = x + dx;
      if (ir(ty, tx) && nz(ty, tx) && abs(g[y][x] - g[ty][tx]) == 1) {
        return false;
      }
    }
  }

  for (int ny = 0; ny < N; ny++) {
    for (int nx = 0; nx < M; nx++) {
      if (!nz(ny, nx)) {
        g[ny][nx] = fr + 1;
        if (brute(ny, nx, fr + 1)) return true;
        g[ny][nx] = 0;
      }
    }
  }

  return false;
}

void printSol() {
  cout << "YES\n";
  for (int y = 0; y < N; y++) {
    for (int x = 0; x < M; x++) {
      cout << g[y][x] << " ";
    }
    cout << "\n";
  }
}

void solve() {
  int n, m;
  cin>>n>>m;
  N = n;
  M = m;

  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      g[y][x] = 0;
    }
  }

  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      g[y][x] = 1;
      bool works = brute(y, x, 1);
      if (works) {
        printSol();
        return;
      }
      g[y][x] = 0;
    }
  }

  cout << "NO\n";
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t; cin >> t;
  while (t--) {
    solve();
  }
}

Test 1

Verdict: ACCEPTED