Zadanie

Miška veľmi rada vymýšľa. Prednedávnom si chcela zaobstarať novú malú mačku a jej priateľ musel vynaložiť všetky svoje sily na to, aby ju prehovoril, že je to hlúposť. Teraz si vymyslela, že sa jej nepáči, ako vyzerá jej terasa.

Miškina terasa sa skladá z \(N \times M\) rovnako veľkých štvorcových kachličiek, ktoré tvoria obdĺžnik. Aktuálne majú všetky kachličky jednu z dvoch farieb - ružovú alebo fialovú. Miška je s farbami spokojná, chce však, aby jej terasa vyzerala trocha inak. Chce, aby sa žiadne dve kachličky s rovnakou farbou nedotýkali hranou (rohom môžu). Keďže hádať sa s Miškou je ťažšie než jednoducho premaľovať terasu, Miškin priateľ by rád vedel, koľko najmenej kachličiek treba premaľovať, aby bola Miška spokojná.

Formát vstupu

V prvom riadku vstupu dostanete dve čísla \(n\) (\(1 \leq n \leq 10^6\)) - výšku terasy, a \(m\) (\(1 \leq m \leq 10^6\)) - šírku terasy.

Nasleduje \(n\) riadkov. V každom riadku je reťazec dĺžky \(m\) pozostávajúci z písmeniek \(r\) (ružová kachlička) alebo \(f\) (fialová kachlička).

V sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq N \times M \leq\) \(20\) \(10^3\) \(10^5\) \(10^6\)

Formát výstupu

Na jeden riadok vypíšte jedno číslo - koľko najmenej kachličiek musíme premaľovať tak, aby sa žiadne dve kachličky rovnakej farby nedotýkali hranou.

Príklad

Input:

1 1
r

Output:

0

Tu netreba prefarbovať žiadnu kachličku.

Input:

2 3
rfr
frf

Output:

0

Taktiež nemusíme nič prefarbovať.

Input:

2 2
rf
rr

Output:

1

Potrebujeme prefarbiť ľavé dolné políčko na fialové, čo je jedno prefarbenie.

Zaujímavá myšlienka

Dôležité je si hneď na začiatku uvedomiť, že Miškina podmienka – žiadne dve kachličky dotýkajúce sa hranou nemôžu mať rovnakú farbu – v kombinácii s tým, že máme iba dve farby, znamená, že výsledná terasa bude vyzerať ako šachovnica. Ďalej si môžeme všimnúť, že z tohto dôvodu existujú iba dva finálne stavy po tom, čo by sme všetky potrebné kachličky premaľovali. Buď bude v ľavom hornom rohu ružová farba, alebo fialová. Zvyšok je v podstate daný týmto jedným rozhodnutím.

Optimálne riešenie

Na riešenie problému môžeme pristúpiť tak, že si rozdelíme políčka na šachovnici do dvoch skupín. Nazvime ich párne a nepárne, pričom medzi párne zaradíme ľavé horné políčko spolu so všetkými ďalšími, ktoré by na šachovnici mali rovnakú farbu.

Ak si zvolíme, že v ľavom hornom rohu má byť ružová kachlička, vieme spočítať, na koľkých párnych políčkach sú fialové a na koľkých nepárnych sú ružové. Súčet týchto dvoch čísel predstavuje počet kachličiek, ktoré by sme museli premaľovať. Podobne si môžeme vypočítať, koľko by sme museli premaľovať v prípade, že v ľavom hornom rohu by mala byť fialová kachlička – stačí spočítať počet ružových kachličiek na párnych pozíciách a počet fialových na nepárnych pozíciách.

Nakoniec už len porovnáme, ktoré z týchto dvoch čísel je menšie, a vypíšeme ho. (Poznámka: Nemusíme našou plochou prechádzať dvakrát – stačí raz a údaje si priebežne zapamätáme.)

Časová zložitosť: \(O(N \times M)\), keďže každú kachličku prejdeme raz. Pamäťová zložitosť: \(O(1)\), keďže si pri postupnom načítavaní vstupu stačí pamätať iba počty jednotlivých typov políčok (napr. „párne fialové = 3“), a teda si nemusíme ukladať celý vstup – postačí nám zopár premenných.

n,m = map(int, input().split())
parne = True
slovnik = {'Truer':0, 'Falser':0, 'Truef':0, 'Falsef':0}
for _ in range(n):
    riadok = input()
    for farba in riadok:
        slovnik[str(parne)+farba] += 1
        parne = not parne
    if not m % 2: parne = not parne
zacruzova = slovnik['Truer'] + slovnik['Falsef']
zacfialova = slovnik['Falser'] + slovnik['Truef']

print(min((n*m - zacruzova, n*m - zacfialova)))
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    bool parne = true;
    unordered_map<string, int> slovnik = { {"Truer", 0}, {"Falser", 0}, {"Truef", 0}, {"Falsef", 0} };
    
    for (int i = 0; i < n; ++i) {
        string riadok;
        cin >> riadok;
        
        for (char farba : riadok) {
            string key = (parne ? "True" : "False") + string(1, farba);
            slovnik[key]++;
            parne = !parne;
        }
        
        if (m % 2 == 0) {
            parne = !parne;
        }
    }
    
    int zacruzova = slovnik["Truer"] + slovnik["Falsef"];
    int zacfialova = slovnik["Falser"] + slovnik["Truef"];
    
    cout << min((n * m - zacruzova), (n * m - zacfialova)) << endl;
    
    return 0;
}

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