Zadanie

Povedali ste si niekedy po nástupe do autobusu: “Toľko voľného miesta! Prečo tu nie sú sedadlá?”. Nuž, časy, keď ste boli nútení stáť v poloprázdnom autobuse, budú už čoskoro minulosťou. Prichádza revolúcia v hromadnej doprave.

Na trhu sa totiž objavil superbus – autobus, v ktorom je každý centimeter štvorcový pokrytý čalúnenou sedačkou. Interiér superbusu obsahuje \(n\) radov a v každom z nich je \(m\) sedačiek vedľa seba. Navyše, sedačky nie sú všetky otočené dopredu. Aby si cestujúci mohli vybrať smer, ktorým sa chcú počas jazdy pozerať, v superbuse sú sedadlá pootáčané do každého zo 4 smerov.

Pri prvom testovaní superbusu sa ale zistilo, že má jednu fatálnu chybu – niektoré sedačky sú otočené čelom k sebe. A keď sú obe obsadené, niet miesta pre nohy cestujúcich.

Dizajnér superbusu preto potrebuje niektoré sedačky otočiť niekoľkokrát o deväťdesiat stupňov tak, aby žiadne dve sedačky neboli k sebe otočené čelom. Nakoľko už bolo vyrobených veľa superbusov, v každom z nich bude nutné tieto sedačky otočiť. To je veľa roboty – je preto žiadúce, aby bolo potrebné sedačky otáčať čo najmenejkrát.

Úloha

Na vstupe je mriežka, v ktorej je každé políčko – sedadlo – otočené na sever, východ, juh alebo na západ.

O mriežke hovoríme, že je v dobrom stave práve vtedy, keď žiadne dve susedné sedadlá nie sú natočené proti sebe.

V jednom kroku je povolené otočiť niektoré sedadlo o deväťdesiat stupňov doľava alebo doprava. Zistite, koľko najmenej krokov je potrebných na to, aby sme mriežku dostali do dobrého stavu.

Netradične vám k tejto úlohe naznačíme riešenie. Ak nápovedu nechcete vedieť, nepozerajte do poznámky pod čiarou. Ak si s úlohou neviete poradiť, možno vám poznámka pod čiarou1 pomôže.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(1 \leq n, m \leq 50\) – rozmery mriežky.

Nasleduje \(n\) riadkov, na každom z nich je \(m\) znakov popisujúcich natočenie danej sedačky. Znak ^ zodpovedá natočeniu na sever, > na východ, v na juh, a < na západ.

Formát výstupu

Na výstup vypíšte jedno celé číslo – najmenší počet krokov, na ktorý je možné dostať mriežku do dobrého stavu.

Príklad

Input:

3 3
>v<
>^<
^^^

Output:

2

Otočíme sedadlo v strede prvého riadku dvarát o 90 stupňov.

Input:

1 10
>>><<<>><<

Output:

2

Napríklad môžeme otočiť tretie sedadlo zľava a tretie sedladlo od konca smerom na sever.

  1. Pozor, blíži sa prezradenie nápovedy. Odporúčame naštudovať si riešenie problému minimum-cost maximum flow. Na internete nájdete veľa dobrých aj zlých materiálov k tejto téme. Nezabudnite však, že program, ktorý odovzdáte, musí byť váš vlastný, nie skopírovaný z cudzieho zdroja.↩

Ako vieme zo zadania, rozostavenie stoličiek je vyhovujúce práve vtedy, keď žiadne dve stoličky nie sú otočené oproti sebe. Takže zistiť, či je konkrétne rozostavenie vyhovujúce, vieme nasledovne:

Na začiatku každej stoličke \(A\) priradíme hodnotu \(1\). Následne, v smere, v ktorom je stolička \(A\) otočená, je práve jedna hrana oddeľujúca dve stoličky – stoličku \(A\) od niektorej inej stoličky \(B\). Hrany oddeľujúce dve stoličky budeme volať okraje.

Presunieme hodnotu stoličky \(A\) na ten okraj, v ktorého smere je \(A\) otočená – hodnotu stoličky zmeníme na \(0\), a hodnotu okraju zvýšime o \(1\). Toto zopakujeme pre všetky stoličky. Potom rozostavenie vyhovuje práve vtedy, keď má každý okraj hodnotu najviac \(1\).

Zadanú úlohu potom vieme riešiť pomocou minimum cost maximum flow na nasledovne zostrojenom grafe: Vrcholmi grafu nech sú stoličky a okraje. Do každej stoličky vedie hrana zo zdroja (anglicky source) s kapacitou \(1\) a cenou \(0\). Z každej stoličky vedie hrana s kapacitou \(1\) do štyroch susedných okrajov. Cena každej z týchto hrán je určená tým, koľkokrát musíme stoličku otočiť, aby bola otočená smerom k tomu okraju. Z každého okraja vedie hrana s kapacitou \(1\) do výlevky (anglicky sink).

Rozmyslite si, prečo nám stačí hľadať cenovo najlacnejší maximálny tok – nemôže sa stať, že by tento tok niektorým hranám priradil iné hodnoty ako \(0\) alebo \(1\)?

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