Ruudukko

#include <bits/stdc++.h>

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;

const int inf = 1e9;
const ll LLinf = 1e18;

vector<vector<int>> brute(int n, int m) {
    vector<vector<int>> ret(n, vector<int> (m, -1));

    vector<int> used(n * m + 1);

    auto ok = [&](int y, int x) {
        vector<int> to_comp;
        if (x > 0) to_comp.push_back(ret[y][x - 1]);
        if (x < m - 1) to_comp.push_back(ret[y][x + 1]);
        if (y > 0) to_comp.push_back(ret[y - 1][x]);
        if (y < n - 1) to_comp.push_back(ret[y + 1][x]);

        for (int v : to_comp) {
            if (abs(ret[y][x] - v) == 1) return false;
        }
        return true;
    };

    function<bool(int, int)> solve = [&](int y, int x) {
        if (y == n) {
            assert(x == 0);
            return true;
        } 

        for (int v = 1; v <= n * m; ++v) {
            if (used[v]) continue;
            ret[y][x] = v;
            used[v] = 1;

            if (ok(y, x)) {

                int ny = y, nx = x + 1;
                if (nx == m) {
                    ny++; nx = 0;
                }

                if (solve(ny, nx)) return true;
            }

            used[v] = 0;
            ret[y][x] = -1;
        }

        return false;
    };

    if (solve(0, 0)) return ret;

    return {};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int tt; cin >> tt;
    while (tt--) {
        int n, m;
        cin >> n >> m;
        auto ans = brute(n, m);

        if (ans.empty()) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
            for (auto v : ans) {
                for (int x : v) {
                    cout << x << " ";
                }
                cout << "\n";
            }
        }
    }

}

Test 1

Verdict: ACCEPTED