Zadanie

Korporácia Svetelných Prístrojov konečne predstavila svoj nový produkt. Je ním systém osvetlenia, ktorý sa skladá zo žiaroviek usporiadaných do mriežky \(n\times m\) a ku každej žiarovke prislúcha jedno tlačidlo, ktoré ju má prepínať.

Keď už bola výroba v plnom prúde, zistili, že niekomu z Federácie Kazisvetov a Sabotérov sa podarilo prepísať ich schémy, a teda všetky vyrobené kusy obsahujú chybu. Konkrétne, keď prepnete niektorú žiarovku, prepnú sa aj všetky susedné žiarovky (za susedné považujeme \(4\) žiarovky, ktoré sú od nej hore, dole, napravo a naľavo). Čo spraviť so všetkými týmito vadnými kusmi? Začali ich predávať ako špeciálnu edíciu.

Po krátkom čase bol ich technical support zahltený požiadavkami typu: “Dá sa nejak zapnúť táto a hentá a tamtá a ešte tieto tu žiarovky?”. Samozrejme, nikto nemá čas tieto požiadavky riešiť, a preto potrebujú vašu pomoc.

Úloha

Na vstupe dostanete požadovaný stav, ktoré žiarovky majú byť zapnuté a ktoré vypnuté. Na začiatku sú všetky žiarovky vypnuté a vašou úlohou je zistiť, ktoré tlačidlá treba stlačiť, aby sa žiarovky dostali do požadovaného stavu.

Formát vstupu

Na prvom riadku dostanete dve celé čísla (\(1 \le n, m \le 30\)). Nasleduje \(n\) riadkov, ktoré popisujú mriežku žiaroviek. Každý z nich sa skladá z \(m\) čísel, ktoré môžu byť \(0\) alebo \(1\). \(0\) znamená, že daná žiarovka má byť vypnutá a \(1\) znamená, že daná žiarovka má byť zapnutá.

Formát výstupu

Ak riešenie neexistuje, vypíšte \(-1\).

Ak existuje, vypíšte \(n\) riadkov po \(m\) čísel. Vypíšte \(0\), ak tlačidlo, ktoré patrí žiarovke na danom mieste, nemá byť stlačené a \(1\), ak má byť stlačené.

Hodnotenie

Sú \(4\) sady vstupov. Platia v nich nasledovné obmedzenia: 1. \(n, m \le 10\) 2. \(n, m \le 20\) 3. \(n, m \le 30\), existuje vždy práve jedno riešenie 4. \(n, m \le 30\)

Príklady

Input:

3 3
1 1 1
1 1 1
1 1 1

Output:

1 0 1
0 1 0
1 0 1

Input:

3 2
0 1
0 0
1 1

Output:

-1

V tejto úlohe bolo treba určiť, ktoré tlačidlá, prepínajúce žiarovku spolu s jej susedmi, treba stlačiť, aby sme dosiahli požadovanú konfiguráciu zapnutých žiaroviek.

Pomalšie riešenie

Dôležité pozorovanie je, že keď si zafixujeme, ktoré tlačidlá v prvom riadku stlačíme, zvyšok je už jednoznačný. Pozrime sa na žiarovky v prvom riadku potom, ako stlačíme tlačidlá v prvom riadku. Niektoré sú v správnom stave a niektoré sú v nesprávnom. Tie žiarovky, ktoré sú nesprávne, musíme ešte prepnúť a jediné tlačidlo ktoré ešte môžeme použiť je to priamo pod ňou (tlačidlá v prvom riadku máme zafixované). Naopak, tlačidlo pod správnou žiarovkou nesmieme prepnúť, lebo by sme ju prepli do nesprávneho stavu. To nám jednoznačne určuje, ktoré tlačidlá v druhom riadku treba stlačiť.

Takto môžeme pokračovať. Teraz každú žiarovku v druhom riadku vieme prepnúť len tlačidlom priamo pod (tie v prvom a druhom riadku sú určené) a teda vieme, ktoré tlačidlá v treťom riadku treba stlačiť.

Toto opakujeme postupne pre všetky riadky, až kým určíme ktoré všetky tlačidlá budú stlačené.

Stačí nám teda vyskúšať všetky možnosti pre prvý riadok, podľa vždy toho určiť zvyšok a skontrolovať, či dosiahneme, že všetky žiarovky sú správne.

Dokopy je \(2^m\) možností pre prvý riadok. Každú možnosť vyskúšame v \(O(nm)\). Časová zložitosť tohto riešenia je \(O(2^nnm)\).

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

int main() {
	int n, m;
    cin >> n >> m;
    vector<vector<int>> ziarovky(n, vector<int>(m));
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> ziarovky[i][j];
    int N = (1<<m);
    for(int start = 0; start < N; start++) {
        bool ok = true;
        vector<vector<int>> prep(n, vector<int>(m, 0));
        for(int i = 0; i < m; i++) prep[0][i] = (bool)(start&(1<<i));
        vector<vector<int>> z(n, vector<int>(m));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(prep[i][j]) {
                    z[i][j] = !z[i][j];
                    if(j) z[i][j-1] = !z[i][j-1];
                    if(j < m - 1) z[i][j+1] = !z[i][j+1];
                    if(i < n - 1) z[i+1][j] = !z[i+1][j];
                }
            }
            for(int j = 0; j < m; j++) {
                if(i < n - 1) prep[i+1][j] = (z[i][j] != ziarovky[i][j]);
                else {
                    if(z[i][j] != ziarovky[i][j]) ok = false;
                }
            }
        }
        if(ok) {
            for(auto x : prep)
                for(int i = 0; i < m; i++)
                    cout << (bool)(x[i]) << (i == m - 1 ? '\n' : ' ');
            return 0;
        }
    }
    cout << "-1\n";
}

Zrýchlenie

Toto riešenie vieme zrýchliť pomocou bitovej mágie. Každý riadok žiaroviek budeme reprezentovať jedným číslom, ktorého binárna reprezentácia hovorí o tom, ktoré žiarovky sú zapnuté a ktoré sú vypnnuté. Tak isto budeme reprezentovať stlačené a nestlačené tlačidlá.

Potom pomocou bitových operácií (^, <<, >>, &, |) vieme vyhodnotiť každý riadok v konštantnom čase: 1. Máme číslo ktoré reprezentuje tlačidlá ktoré chceme stlačiť, nazvime ho \(s\). Na základe toho chceme aktualizovať aktuálny stav žiaroviek. Riadok nad a riadok pod nám stačí zmeniť na xor (^) hodnoty toho riadku a \(s\). Takto sa zmenia bity na tých miestach, kde boli jednotky v \(s\). V aktuálnom riadku potrebujeme prepnúť žiarovky na miestach kde bolo stlačené tlačidlo a ešte naľavo a napravo od nich. Najprv na riadok aplikujeme xor s \(s\), čím prepneme tie na stlačených miestach. Potom môžeme použiť bitový posun doprava a doľava (>>, <<) na to, aby sme dostali jednotky na pozíciach napravo a naľavo od stlačených tlačidiel. Riadok teda ešte prexorujeme s>>1 a s<<1, čím prepneme tieto žiarovky. Nakoniec si treba dať pozor aby sme odstránili jednotky za \(m\)-tou pozíciou, ktoré mohli vzniknúť bitovým posunom. Na to použijeme and (&) s číslom (1<<m)-1, ktoré má jednotky na prvých \(m\) pozíciach. 2. Ako druhý krok musíme porovnať aktuály stav žiaroviek s očakávaným stavom žiaroviek, aby sme zistili, ktoré tlačidlá v ďalšom riadku treba stlačiť. Na to použijeme znova xor aktuálneho stavu s očakávaným stavom. Na miestach kde sa líšia dostaneme \(1\) a na ostatných miestach \(0\).

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

int main() {
	int n, m;
    cin >> n >> m;
    vector<int> correct(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            correct[i] += x<<j;
        }
    }
    int N = (1<<m);
    for(int start = 0; start < N; start++) {
        vector<int> prep(1, start);
        int next = 0;
        for(int i = 0; i < n; i++) {
            int cur = next;
            cur ^= prep[i] ^ (prep[i]>>1) ^ (prep[i]<<1) & (N-1);
            next = prep[i];
            prep.push_back(cur ^ correct[i]);
        }
        if(prep.back() == 0) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    cout << (bool)(prep[i] & (1<<j)) << (i == m - 1 ? '\n' : ' ');
                }
            }
            return 0;
        }
    }
    cout << "-1\n";
}

Vzorové riešenie

Označme si \(z_{i,j}\) požadovaný stav žiarovky (\(0\) = vypnutá, \(1\) = zapnutá) v riadku \(i\) a stĺpci \(j\), ktorý dostaneme na vstupe. Podobne si označme \(t_{i,j}\) stav tlačidla (\(0\) = stlačené, \(1\) = nestlačené) v riadku \(i\) a stĺpci \(j\).

Celú úlohu teraz vieme zapísať pomocou sústavy lineárnych rovníc modulo \(2\). Hľadáme také hodnoty premenných \(t_{i,j}\), aby platili rovnice typu:

\(t_{i,j}+t_{i+1,j}+t_{i-1,j}+t_{i,j+1}+t_{i,j-1} \equiv z_{i,j}\ (\textrm{mod}\ 2)\)

To znamená, že z tých piatich tlačidiel, ktoré vedia prepnúť danú žiarovku, musí byť počet stlačených modulo \(2\) rovnaký, ako požadovaný stav žiarovky.

Na vyriešenie takejto sústavy rovníc môžeme použiť Gaussovu eliminačnú metódu. Treba len dať pozor na to, že sme modulo \(2\), teda \(1+1=0\) a podobne.

Gaussova eliminácia pri \(k\) rovniciach o \(k\) neznámych má časovú zložitosť \(O(k^3)\). V našom prípade je \(k=nm\), teda časová zložitosť celého prgramu je \(O((nm)^3)\).

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

vector<int> solve(vector<vector<int>> matrix) {
    int n = matrix.size();
    vector<int> finished(n, -1);
    for(int j = 0; j < n; j++) {
        for(int i = 0; i < n; i++) {
            if(matrix[i][j] && finished[i] == -1) {
                for(int ii = 0; ii < n; ii++) {
                    if(ii == i) continue;
                    if(matrix[ii][j] == 0) continue;
                    for(int jj = j; jj <= n; jj++) {
                        matrix[ii][jj] ^= matrix[i][jj];
                    }
                }
                finished[i] = j;
                break;
            }
            if(i == n-1) {
                for(int ii = 0; ii < n; ii++) matrix[ii][j] = 0;
            }
        }
    }
    vector<int> solutions(n, 0);
    for(int i = 0; i < n; i++) if(finished[i] != -1) solutions[finished[i]] = matrix[i][n];
    for(int i = 0; i < n; i++) {
        if(finished[i] == -1) {
            int x = 0;
            for(int j = 0; j < n; j++) x ^= (matrix[i][j] & solutions[j]);
            if(x != matrix[i][n]) return {}; 
        }
    }
    return solutions;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n*m, vector<int>(n*m+1, 0));
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
        int id = i*m+j;
        cin >> matrix[id][n*m];
        matrix[id][id] = 1;
        if(i > 0) matrix[id][id-m] = 1;
        if(i < n-1) matrix[id][id+m] = 1;
        if(j > 0) matrix[id][id-1] = 1;
        if(j < m-1) matrix[id][id+1] = 1;
    }
    vector<int> sol = solve(matrix);
    if(sol.size() == 0) cout << "-1\n";
    else for(int i = 0; i < n*m; i++) cout << sol[i] << ((i+1) % m ? " " : "\n");
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.