Teselas-Tarche

#include <bits/stdc++.h>

using namespace std;

int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

void intercambiar(int fila1, int columna1, int fila2, int columna2);

struct llamada {
    int a, b, c, d;
};

int teselas(vector<string> &mosaico) {
    int n = (int)mosaico.size();
    int m = (int)mosaico[0].size();
    vector<int> amount(26, 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            amount[mosaico[i][j] - 'a']++;
        }
    }

    if (n % 2 == 0) n--;
    if (m % 2 == 0) m--;

    int maxAmount = ((n - 1) / 2 + 1) * ((m - 1) / 2 + 1);
    for (int i = 0; i < 26; i++) {
        if (amount[i] > maxAmount) return 0;
    }

    n = (int)mosaico.size();
    m = (int)mosaico[0].size();

    vector<string> nuevo(n, string(m, ' '));

    priority_queue<pair<int, char>> letras;
    for (int a = 0; a < 26; a++)
        if (amount[a] != 0)
            letras.push({amount[a], 'a' + a});

    while (!letras.empty()) {
        auto curr = letras.top();
        letras.pop();
        bool done = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (nuevo[i][j] != ' ') continue;
                bool possible = true;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x < 0 || y < 0 || x >= n || y >= m) continue;
                    if (nuevo[x][y] == curr.second) possible = false;
                }
                if (possible) {
                    nuevo[i][j] = curr.second;
                    done = true;
                    break;
                }
            }
            if (done) break;
        }
        if (curr.first > 1) letras.push({curr.first - 1, curr.second});
    }

    vector<vector<bool>> cambio(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mosaico[i][j] != nuevo[i][j]) cambio[i][j] = true;
        }
    }

    queue<llamada> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!cambio[i][j]) continue;
            for (int a = 0; a < n; a++) {
                bool cambiada = false;
                for (int b = 0; b < m; b++) {
                    if (!cambio[a][b]) continue;
                    if (mosaico[a][b] == nuevo[i][j]) {
                        ans.push({i, j, a, b});
                        cambio[i][j] = false;
                        mosaico[a][b] = mosaico[i][j];
                        mosaico[i][j] = nuevo[i][j];
                        if (mosaico[a][b] == nuevo[a][b]) cambio[a][b] = false;
                        cambiada = true;
                        break;
                    }
                }
                if (cambiada) break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (cambio[i][j])
                return 0;
        }
    }

    while (!ans.empty()) {
        auto curr = ans.front();
        ans.pop();
        intercambiar(curr.a, curr.b, curr.c, curr.d);
    }

    return 1;
}