Koniec kola: 11. február 2019 23:59
20 days
Počet bodov:
Popis:  12b
Program:  8b

Paulínka si ako každý čerstvý vysokoškolák dopraje dostatočné a zdravé množstvo spánku. Navyše, v záchvate mánie (nebojte sa, mánia už dávno skončila) začala jesť na večeru divné veci. Kombináciou týchto javov sa jej uprostred noci sníval prečudesný sen. Ocitla sa na ostatnom Letnom Tábore Trojstenu (na tom o Power Rangeroch), kde sa práve na poli hrala hra – strategická behačka.

Družinky účastníkov bojovali o ovládnutie políčok veľkého energetického poľa, ktoré bolo rozdelené na štvorčeky. Prebiehalo to tak, že družinky vysielali svojich rangerov na behy skrz štvorcovú mriežku. Títo rangeri mohli behať iba pozdĺž osí mriežky a nemohli meniť smer. Navyše, aby sa náhodou nezrazili, mohol bežať iba jeden ranger naraz.

Rangeri boli, samozrejme, farební. Keď ranger prebehol cez políčko, políčko sa sfarbilo jeho farbou, a tak bolo ihneď viditeľné, že políčko začalo patriť jeho družinke. Políčka na začiatku hry nemali žiadnu farbu. Aj keď ranger prebehol po už zafarbenom políčku, toto políčko po prebehnutí farbu zmenilo.

Paulínka na túto hru prišla neskoro a celkom by ju zaujímalo, akú časť hry prespala. Na základe ofarbeného poľa zistite, koľko najmenej kôl muselo prebehnúť od začiatku hry do momentu, kedy Paulínka prišla.

Úloha

Dostanete mriežku rozmerov \(r \times s\), ktorá je na každom políčku ofarbená jednou farbou. Táto mriežka bola na začiatku hry čistá. Potom prebehlo \(k\) kôl. V každom kole sa prefarbil práve jeden celý stĺpec alebo riadok tejto mriežky jednou farbou. Na základe výsledného ofarbenia zistite, koľko najmenej kôl mohlo prebehnúť, teda minimálne možné \(k\).

Formát vstupu

V prvom riadku vstupu sú dve čísla: \(r, s (1 \leq r, s \leq 200)\), počet riadkov a stĺpcov mriežky. Každý z nasledujúcich \(r\) riadkov obsahuje \(s\) čísel oddelených medzerami \(f_i; 0 \leq f_i \leq r \cdot s\), ktoré popisujú farby jednotlivých políčok mriežky.

Farby používajú celý rozsah čísel na vstupe. Inými slovami, ak sa vo vstupe vyskytuje farba číslo \(f\), určite sa vo vstupe nachádzdzajú aj farby \(0, 1, \dots, f-1\).

Vo vstupoch je tiež garantované, že tabuľka vznikla podľa pravidiel hry.

Formát výstupu

Na výstup vypíšte jedno číslo \(k\), minimálny počet ofarbení stĺpca/riadku potrebných na dosiahnutie ofarbenia tabuľky. ## Hodnotenie Vaše riešenia budú testované na štyroch sadách testovacích vstupov, pre ktoré platí:

Sada 1 2 3 4
Maximálne \(r + s\) \(10\) \(20\) \(200\) \(300\)

Príklady

Input:

2 5
0 0 1 1 1
0 0 1 1 1

Output:

4

V optimálnom prípade ofarbíme najprv oba riadky farbou \(1\) a potom prvé dva stĺpce farbou \(0\).

Input:

4 4
0 0 0 0
1 4 4 3
1 5 6 3
1 2 2 2

Output:

7

Ofarbujeme postupne: tretí riadok farbou \(6\), druhý stĺpec \(5\), druhý riadok \(4\), štvrtý stĺpec \(3\), posledný riadok \(2\), prvý stĺpec \(1\), prvý riadok \(0\).

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.