Zadanie

Prvácky týždeň na Matfyze je v plnom prúde. Budúci študenti (medzi ktorými je mimochodom aj Duško) si užili mnoho prednášok, spoznávacích hier a iných blbostí, ktoré Dušan už dávno poznal (veď Matfyz je už dávno jeho druhým domovom a do T2 už chodí aj spávať). Takto znudený sa teda rozhodol, že na budúcich študenton FIIT-ky nastraží habaďúru. Počas spoločnej zoznamovačky sa nenápadne vytratil a začal snovať plán, ako uväzniť FIITákov na Matfyze. A čo je ešte lepšie, o chvíľu bude obed a ak cesty zatarasí dostatočne dobre, tak FIITáci nestihnú prísť do Eat&Meetu 1 načas. Treba si len dať pozor na to, aby nevymkol aj nejakého zo svojich kamarátov.

Úloha

Pôdorys Matfyzu si vieme predstaviť ako štvorčekovú mriežku s \(n\) riadkami a \(m\) stĺpcami. Každé políčko môže byť zablokované #, prázdne . alebo na ňom môže stáť človek ( F ak to je FIITák alebo M ak je Matfyzák). V pravom dolnom rohu mapky sa nachádza východ, cez ktorý sa dá dostať do Eat&Meetu. Dušan chce na FIITákov nastražiť nasledovnú habaďúru. Zablokuje nejaké prázdne políčka Matfyzu tak, aby sa žiaden FIITák nevedel dostať von z Matfyzu, ale každý Matfyzák sa z neho vedel dostať. Každý človek vie chodiť len po hranou susediacich políčkach. Pomôžte Dušanovi zistiť, ktoré políčka má zablokovať alebo povedzte, že sa to proste nedá.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1 \leq n, m \leq 600\)) udávajúce rozmery Matfyzu. Nasleduje \(n\) riadkov a na každom z nich \(m\) znakov ., #, M alebo F popisujúce aktuálny stav Matfyzu a rozmiestnenie ľudí. Je garantované, že pravé dolné políčko (teda východ) je vždy prázdne.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq n,m \leq\) \(4\) \(25\) \(100\) \(600\)

Formát výstupu

Vypíšte Plan uspesny, ak sa dajú zablokovať niektoré políčka tak, aby sa všetci Matfyzáci vedeli dostať z Matfyzu von a všetci FIITáci nie. Potom vypíšte \(n\) riadkov a na každom z nich \(m\) znakov reprezentujúcich to, ako môže vyzerať Matfyz po pridaní prekážok, aby Dušanova habaďúra vyšla. Ak existuje viac možností, vypíšte ľubovoľnú z nich. Ak sa to nedá, vypíšte len na jeden riadok Neda sa.

Nezabudnite posledný riadok ukončiť znakom konca riadku.

Príklady

Input:

3 3
M..
..F
M..

Output:

Neda sa

Jediný spôsob, ako zabrániť FIITákovi sa dostať z univerzity von je, ak zablokujeme východ. Potom sa ale z univerzity nebudú vedieť dostať ostatní Matfyzáci.

Input:

5 5
...F.
F....
..###
##M..
M....

Output:

Plan uspesny
...F.
F....
..###
##M..
M....

Netreba pridávať žiadne prekážky, žiaden FIITák sa nedokáže dostať z univerzity.

Input:

2 5
F.MMM
.F.M.

Output:

Plan uspesny
F#MMM
.F#M.

Bruteforce

V prvej sade sú limity celkom malé, teda si môžeme dovoliť vygenerovať všetky možné výsledné plány Matfyzu a následne zistiť, či aspoň jeden z nich vyhovuje zadaniu. Na takéto generovanie môžeme použiť napríklad techniku bitmasiek, kde si vygenerujeme postupne všetky \(n \cdot m\) bitové čísla a podľa nich vygenerujeme zábrany. Ak je nejaký bit 1, tak na dané miesto v pláne Matfyzu dáme zábranu (ak sa to teda dá), inak ju tam nedáme. Potom nám už len zostáva skontrolovať podmienky zo zadania.

Pre každého Matfyzáka z jeho pozície môžeme spustiť prehľadávanie do širky (alebo aj do hĺbky). Ak sa týmto prehľadávaním dostaneme do pravého dolného rohu Matfyzu, tak sa vedia dostať von. Podobne to spravíme aj pre každého FIITáka. Ak sa každý Matfyzák a žiaden FIITák dokáže dostať von, tak sme našli správne riešenie, inak je aktuálne riešenie nesprávne. Pre každého človeka potrebujeme spustiť prehľadávanie, ktoré má časovú zložitosť \(O(n \cdot m)\). Ľudí ale môže byť až \(n \cdot m\), teda časová zložitosť kontroly jedného plánu je \(O(n^2 \cdot m^2)\). Keďže všetkých podmnožín \(n \cdot m\) prvkovej množiny je \(2^{n \cdot m}\), tak celková časová zložitosť je \(O(n^2 \cdot m^2 \cdot 2^{n \cdot m})\).

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

vector<int> dx{0, 0, 1, -1}, dy{1, -1, 0, 0};

int main(){
    int n,m;cin>>n>>m;
    vector<string> mapa(n);
    for(string &riadok : mapa)
        cin>>riadok;
    // zisti, ci je policko v mriezke
    auto v_mriezke = [&](int x,int y){return x < m && x >= 0 && y < n && y >= 0;};

    // z vyplnenej tabulky zisti, ci je podla zadania spravna
    auto check = [&](vector<string> &tmp_mapa){
        for(int start_y = 0;start_y < n;start_y++){
            for(int start_x = 0;start_x < m;start_x++){
                char policko = tmp_mapa[start_y][start_x];
                if(policko != 'M' && policko != 'F')
                    continue;
                bool dostanem_sa_von = false;
                vector<vector<int>> preskumane(n,vector<int>(m,false));
                queue<pair<int,int>> q;
                q.push({start_y,start_x});
                while(!q.empty()){
                    int x,y;
                    tie(y,x) = q.front();
                    q.pop();
                    if(preskumane[y][x] || tmp_mapa[y][x] == '#')
                        continue;
                    preskumane[y][x] = true;
                    if(x == m-1 && y == n-1)
                        dostanem_sa_von = true;
                    for(int smer = 0;smer < 4;smer++){
                        int x2 = x + dx[smer],y2 = y + dy[smer];
                        if(v_mriezke(x2,y2) && !preskumane[y2][x2])
                            q.push({y2,x2});
                    }
                }
                // ak sa vie FIITak dostat von alebo sa matfyzan nevie dostat von
				// tak mame nespravne riesenie
                if((!dostanem_sa_von && policko == 'M') ||
					(dostanem_sa_von && policko == 'F'))
                    return false;
            }
        }
        return true;
    };

    for(int mask = 0;mask < 1<<(n*m);mask++){
        vector<string> tmp_mapa = mapa;
        for(int y = 0;y < n;y++){
            for(int x = 0;x < m;x++){
                if(mask & 1<<(y*m + x) && mapa[y][x] == '.'){
                    tmp_mapa[y][x] = '#';
                }
            }
        }
        if(check(tmp_mapa)){
            cout << "Plan uspesny\n";
            for(string r : tmp_mapa)
                cout << r << "\n";
            return 0;
        }
    }
    cout << "Neda sa\n";
}

Ako lepšie zablokovať FIITákov?

Ako prvé si môžeme všimnúť, že ak má byť plán úspešný, tak vo výslednom pláne Matfyzu nemôže existovať nezablokovaná cesta medzi FIITákom a Matfyzákom. Ak by taká existovala, tak FIITák príde za Matfyzákom a od teraz ho bude len nasledovať. Potom sa buď nevie dostať Matfyzák von z budovy alebo sa FIITák dokáže dostať z budovy. Teda aspoň jedna z podmienok zo zadania nebude splnená. Teda ak sa na začiatku vedľa seba nachádza nejaký FIITák a Matfyzák, tak riešenie určite neexistuje.

Skúsme sa teraz zamyslieť nad tým, ako zabrániť FIITákom dostať sa von z budovy. Povedzme, že to spravíme najjednoduchším spôsobom, akým to ide a všetky 4 políčka okolo každého FIITáka zablokujeme (ak sa tam už niečo nenachádza). Takto od seba oddelíme FIITákov od Matfyzákov (ak nejakí nezačínali vedľa seba) a zablokujeme im východ zo školy.

Nájsť takýmto spôsobom zátarasy má časovú zložitosť \(O(n \cdot m)\), lebo stačí raz prejsť celú tabuľku.

Kontrolovať riešenie môžeme rovnakým spôsobom, ako v bruteforce riešení. Výsledná časová zložitosť potom bude \(O(n^2 \cdot m^2)\), čo stačí na prejdenie prvých 2 až 3 sád.

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

vector<int> dx{0, 0, 1, -1}, dy{1, -1, 0, 0};

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> mapa(n);
    for (auto &riadok: mapa)
        cin >> riadok;

    auto v_mriezke = [&](int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; };

    // obkolesenie FIITakov
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            if (mapa[y][x] != 'F')
                continue;
            for (int smer = 0; smer < 4; smer++) {
                int x2 = x + dx[smer], y2 = y + dy[smer];
                if (!v_mriezke(x2, y2))
                    continue;
                if (mapa[y2][x2] == 'M') {
                    cout << "Neda sa\n";
                    return 0;
                } else if (mapa[y2][x2] != 'F')
                    mapa[y2][x2] = '#';
            }
        }
    }

    // pomocou BFS zistime, ci sa vie dany clovek dostat von
    for (int start_y = 0; start_y < n; start_y++)
        for (int start_x = 0; start_x < m; start_x++) {
            if (mapa[start_y][start_x] == 'F' || mapa[start_y][start_x] == 'M') {
                bool dostanem_sa_von = false;
                vector<vector<int>> preskumane(n, vector<int>(m, false));
                queue<pair<int, int>> q;
                q.push({start_y, start_x});
                while (!q.empty()) {
                    int y, x; tie(y, x) = q.front(); q.pop();
                    if (preskumane[y][x] || mapa[y][x] == '#')
                        continue;
                    if (y == n - 1 && x == m - 1) { // dokazeme sa dostat k vychodu
                        dostanem_sa_von = true;
                        break;
                    }
                    preskumane[y][x] = true;
                    for (int smer = 0; smer < 4; smer++) {
                        int x2 = x + dx[smer], y2 = y + dy[smer];
                        // prehladavame len ak sa nachadzame v mriezke
                        if (v_mriezke(x2, y2) && !preskumane[y2][x2])
                            q.push({y2, x2});
                    }
                }
                if ((mapa[start_y][start_x] == 'F' && dostanem_sa_von) ||
                    (mapa[start_y][start_x] == 'M' && !dostanem_sa_von)) {
                    cout << "Neda sa\n";
                    return 0;
                }
            }
        }
    cout << "Plan uspesny\n";
        for (auto &riadok: mapa)
            cout << riadok << "\n";
}

Prečo toto funguje?

Predstavme si, že sme takto obkolesili každého FIITáka, teda sa žiaden z nich nedokáže dostať von. Teda ak nie je naše riešenie správne, tak sme museli zablokovať aspoň jedného z Matfyzákov (takého, ktorý sa predtým vedel dostať von). Ak by sme chceli tohto Matfyzáka odblokovať, tak musíme aspoň jednu zo zábran, ku ktorej sa tento Matfyzák vie dostať odstrániť, aby mohol prejsť ďalej. Potom ale určite existuje nezablokovaná cesta medzi FIITákom a Matfyzákom, lebo nami pridané zábrany susedia priamo z FIITákmi. Teda riešenie by aj tak neexistovalo.

Optimálne riešenie

Zisťovanie, či je dané riešenie správne, je zatiaľ príliš pomalé. Ako by sa teda dalo zrýchliť? Asi by bolo treba spúšťať len jedno prehľadávanie. Spravíme to teda opačne a prehľadávanie spustíme z pravého dolného rohu Matfyzu. Počas tohto prehľadávania budeme počítať, na koľko Matfyzákov sme zatiaľ narazili. Keďže sa dá dostať z východu k danému Matfyzákovi, tak sa dá aj od toho Matfyzáka dostať k východu. Teda stačí len porovnať celkový počet Matfyzákov na začiatku s počtom Matfyzákov, ktorých sme prešli pri prehľadávaní. Keďže spúšťame už len jedno prehľadávanie, tak toto riešenie už bude mať časovú zložitosť \(O(n \cdot m)\) a pamäťovú zložitosť \(O(n \cdot m)\), teda by malo dostať 8 bodov.

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

vector<int> dx{0, 0, 1, -1}, dy{1, -1, 0, 0};
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> mapa(n);
    for (auto &riadok: mapa)
        cin >> riadok;

    auto v_mriezke = [&](int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; };

    // obkolesenie FIITakov a spocitanie poctu Matfyzakov
    int pocet_matfyzakov = 0;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            if (mapa[y][x] == 'F') {
            for (int smer = 0; smer < 4; smer++) {
                int x2 = x + dx[smer], y2 = y + dy[smer];
                if (!v_mriezke(x2, y2))
                    continue;
                if (mapa[y2][x2] == 'M') {
                    cout << "Neda sa\n";
                    return 0;
                } else if (mapa[y2][x2] != 'F')
                    mapa[y2][x2] = '#';
            }
            } else if (mapa[y][x] == 'M')
                pocet_matfyzakov++;
        }
    }

    // BFS z vychodu
    int dosiahnutelni_matfyzaci = 0;
    vector<vector<int>> preskumane(n, vector<int>(m, false));
    queue<pair<int, int>> q;
    q.push({n - 1, m - 1});
    while (!q.empty()) {
        int y, x; tie(y, x) = q.front(); q.pop();
        if (preskumane[y][x] || mapa[y][x] == '#')
            continue;
        preskumane[y][x] = true;
        if (mapa[y][x] == 'M')
            dosiahnutelni_matfyzaci++;
        for (int smer = 0; smer < 4; smer++) {
            int x2 = x + dx[smer], y2 = y + dy[smer];
            // prehladavame len ak sa nachadzame v mriezke
            if (v_mriezke(x2, y2) && !preskumane[y2][x2])
                q.push({y2, x2});
        }
    }

    if (dosiahnutelni_matfyzaci != pocet_matfyzakov)
        cout << "Neda sa\n";
    else {
        cout << "Plan uspesny\n";
        for (auto &riadok: mapa)
            cout << riadok << "\n";
    }
}
#!/usr/bin/env python3
from collections import deque

n, m = map(int, input().split())
mapa = [list(input()) for _ in range(n)]

# pomocne polia na jednoduchsie hladanie susedov daneho policka
dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)


# pomocna funkcia na zistenie, ci je dane policko vnutry mriezky
def v_mriezke(x: int, y: int):
    return 0 <= x < n and 0 <= y < m


# obkolesenie FIITakov a spocitanie poctu Matfyzakov
pocet_matfyzakov = 0
for y in range(n):
    for x in range(m):
        if mapa[y][x] == "F":
            for smer in range(4):
                x2, y2 = x + dx[smer], y + dy[smer]
                if not v_mriezke(y2, x2):
                    continue
                if mapa[y2][x2] == "M":
                    # ak je vedla seba Matfyzak a FIITak, tak riesenie neexistuje
                    print("Neda sa")
                    quit()
                elif mapa[y2][x2] != "F":
                    # treba si dat pozor, aby sme nedali zabranu na policko s FIITakom
                    mapa[y2][x2] = "#"
        elif mapa[y][x] == "M":
            pocet_matfyzakov += 1

# pustime BFS z vychodu
dosiahnutelni_matfyzaci = 0
preskumane = [[0] * m for _ in range(n)]
fronta = deque([(n - 1, m - 1)])

while fronta:
    y, x = fronta.popleft()
    if preskumane[y][x] or mapa[y][x] == "#":
        continue
    preskumane[y][x] = 1
    if mapa[y][x] == "M":
        dosiahnutelni_matfyzaci += 1
    for smer in range(4):
        x2, y2 = x + dx[smer], y + dy[smer]
        if v_mriezke(y2, x2):
            fronta.append((y2, x2))

if dosiahnutelni_matfyzaci != pocet_matfyzakov:
    print("Neda sa")
else:
    print("Plan uspesny")
    for riadok in mapa:
        print("".join(riadok))

Iné zaujímavé riešenie

Môžeme si všimnúť, že to, ako má vyzerať nejaký riadok vo výsledku je jednoznačne určené tým, ako vyzerá riadok nad ním a riadok pod ním. Teda zistiť, kde chceme pridať v aktuálnom riadku zábrany je pomerne jednoduché. Zaujímavejší problém je ale zistiť, či je toto vyplnenie správne alebo nie, ak máme k dispozícií len \(3\) po sebe idúce riadky. Rozdeľme si políčka do komponentov tak, že z každého políčka v komponente sa dá dostať do každého iného v tom komponente. Potom si pre každý riadok stačí pamätať, ktoré políčko patrí do ktorého komponentu a koľko Matfyzákov sa nachádzaz v ktorom komponente. Aby bolo riešenie správne, tak komponent obsahujúci východ z Matfyzu musí obsahovať všetkých Matfyzákov. Ostáva nám už len dopočítať z toho, ako vyzerajú komponenty v predošlom riadku to, ako majú vyzerať v aktuálnom. Komponenty si budeme pamätať v dátovej štruktúre UnionFind, v ktorej vieme v čase \(O(\alpha(n))\) zistiť, v ktorom komponente je prvok alebo spojiť 2 komponenty. (kde \(\alpha(n)\) je inverzná Ackermannova funkcia, ktorá je pre ľubovoľné rozumne predstaviteľné čísla menšia ako \(5\)) Ak sa na políčku \(i\) v aktuálnom riadku nenachádza stena, tak bude v rovnakom komponente, ako políčko \(i\) v predošlom riadku. Potom nám už len stačí spojiť komponenty susedných políčok v aktuálnom riadku a pridať Matfyzákov ku komponentom, do ktorých patria.

Úlohu teda vyriešime v dvoch prechodoch. V prvom zistíme pomocou vyššie uvedeného algoritmu, či riešenie existuje a ak hej, tak ho v druhom prechode nájdeme a vypíšeme. Toto riešenie má síce zanedbateľne horšiu časovú zložitosť \(O(\alpha(m) \cdot n \cdot m)\), ale okrem vstupu si musí pamätať len \(O(m)\) pamäte navyše. A hlavne, ak by ako výstup stačilo iba určiť úspešnosť plánu (keďže výsledný plán je triviálne skonštruovať), postačoval by nám jeden prechod a pamäťová zložitosť by bola iba \(O(m)\).

#include <bits/stdc++.h>
using namespace std;
#define len(x) ((int)(x.size()))

// The time complexity is O(Row*Col*alpha(Col)).
// Take notice of how we often we use find() and join() in the code:
// The UF trees will be at most just a couple of nodes deep at any given time.
// The running time is in our test data between 1x-1.2x of the O(Row*Col) solution.

// negative number parent[x] means root with abs(parent[x]) nodes
// positive number parent[x] means child of parent[x]
struct UF {
    vector<int> parent;
    vector<int> has_matfyz;
    UF() {}
    int find(int x) {
        if (parent[x] < 0)
            return x;
        return parent[x] = find(parent[x]);
    }
    void join(int x, int y) {
        if (x == -1 || y == -1)
            return;
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (parent[x] > parent[y])
            swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
        has_matfyz[x] += has_matfyz[y];
    }
    void make_root(int x) { // make x root of its tree
        int y = find(x);
        if (x == y)
            return;
        parent[x] = parent[y]; // set size
        parent[y] = x;
        has_matfyz[x] = has_matfyz[y];
    }
    void add(int n) {
        parent.resize(len(parent) + n, -1);
        has_matfyz.resize(len(parent), 0);
    }
};

enum {
    EMPTY = 0,
    WALL = -1,
    FIIT = -2,
    MATFYZ = -3,
};

void merge(vector<int>& row1, vector<int>& row2, UF& uf) {
    uf.add(len(row1));
    int Col = len(row1) - 2;
    for (int x = 1; x <= Col; x++) { // fill new row
        int ui = len(uf.parent) / 2 + x;
        uf.parent[ui] = -1;
        uf.has_matfyz[ui] = row2[x] == MATFYZ;
        if (row2[x] != WALL)
            row2[x] = ui;
    }

    for (int x = 1; x <= Col; x++) // merge vertically
        uf.join(row1[x], row2[x]);
    for (int x = 1; x <= Col; x++) // merge horizontally
        uf.join(row2[x], row2[x - 1]), uf.join(row2[x], row2[x + 1]);

    int shift = len(row1);
    for (int i = len(uf.parent) - 1; i > shift; i--) // lets move roots to second row
        if (uf.find(i) < shift)
            uf.make_root(i);
    for (int x = 1; x <= Col; x++) // lets relabel them in preparation for shifting
        if (row2[x] != WALL)
            row2[x] = uf.find(row2[x]) - shift;

    for (int i = shift; i < len(uf.parent); i++) { // shift uf row2 to row1
        uf.parent[i - shift] = uf.parent[i] < 0 ? uf.parent[i] : uf.parent[i] - shift;
        uf.has_matfyz[i - shift] = uf.has_matfyz[i];
    }
    uf.parent.resize(len(uf.parent) - shift); // delete uf row2
}

// wall out empty cells around Fs
bool block_rows(vector<int>& row1, vector<int>& row2, bool wall_fs) {
    int Col = len(row1) - 2;
    for (int x = 1; x <= Col; x++) {
        if (row2[x - 1] == FIIT || row2[x + 1] == FIIT || row1[x] == FIIT) {
            if (row2[x] == 0)
                row2[x] = WALL;
            else if (row2[x] == MATFYZ) // we would block out MATFYZ
                return false;
            if (wall_fs && row1[x] == FIIT) // for simplicity, we replace Fs with walls
                row1[x] = WALL;
        }
        if (row2[x] == FIIT) {
            if (row1[x] == 0)
                row1[x] = WALL;
            else if (row1[x] == MATFYZ) // we would block out MATFYZ
                return false;
        }
    }
    return true;
}

const string chars = ".#FM";
void char_to_int(vector<char>& row, vector<int>& row2) {
    for (int x = 1; x < len(row) - 1; x++)
        row2[x] = -chars.find(row[x]);
}

void print_row(vector<int>& row) {
    for (int x = 1; x < len(row) - 1; x++)
        cout << chars[-row[x]];
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int Row, Col;
    cin >> Row >> Col;

    // We will read it into memory, but use it in single pass when checking
    // and then in single pass when printing
    vector<vector<char>> grid(Row + 2, vector<char>(Col + 2, '#'));
    for (int y = 1; y <= Row; y++)
        for (int x = 1; x <= Col; x++)
            cin >> grid[y][x];

    bool doable = true;
    UF uf;
    uf.add(Col + 2);
    vector<int>
        row1(Col + 2, -1), // done row
        row2(Col + 2, -1), // processing row
        row3(Col + 2, -1); // helper row for preparing row2 (because Fs will be walled out in row2)
    int matfyz_cnt = 0;
    for (int y = 1; y <= Row + 1; y++) { // fully walled last row included
        string chars = ".#FM";
        for (int x = 1; x <= Col; x++) {       // initial fill
            row3[x] = -chars.find(grid[y][x]); // empty=0, wall=-1, fiit=-2, matf=-3
            matfyz_cnt += row3[x] == MATFYZ;
        }
        doable &= block_rows(row2, row3, true);
        if (!doable)
            break;

        merge(row1, row2, uf);
        row1 = row2;
        row2 = row3;
    }

    // notice that corner_group can be -1 if corner is wall, but that can be ok if there are no Ms
    int corner_group = uf.find(row1[Col]);
    doable &= (corner_group == -1 ? 0 : uf.has_matfyz[corner_group]) == matfyz_cnt;
    cout << (doable ? "Plan uspesny\n" : "Neda sa\n");
    if (!doable)
        return 0;

    row1.assign(Col + 2, -1);
    row2.assign(Col + 2, -1);
    for (int y = 1; y <= Row + 1; y++) { // same as above, but instead of merging we print
        string chars = ".#FM";
        for (int x = 1; x <= Col; x++)
            row3[x] = -chars.find(grid[y][x]);
        block_rows(row2, row3, false);

        row1 = row2;
        row2 = row3;
        if (y >= 2)
            print_row(row1);
    }
}

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ť.