Koniec kola: 29. august 2022 23:59
13 dní
Počet bodov:
Popis:  12b
Program:  8b

Kika sedí v T2-ke1 a rozmýšľa, čo bude dnes robiť. Na Ufe už bola, zvieratá v ZOO už tiež videla a aj všetky obchody už pobehala. Pri rozmýšľaní o svojom ďalšom programe si uvedomila, že vedúci majú v T2-ke ich vlastný program – idú ju prerobiť a popresúvať nábytok.

Jooj, no pri tom sa Kike fakt nechce byť. Tak si povie, že odíde skôr, ako ostatní prídu. Tento plán ale preruší jej potreba idenia na záchod. A čo je horšie, na chodbe už počuje hlasy vedúcich, čiže, ak by na záchod aj šla, tak ich stretne a oni ju pošlú naspäť, aby im pomohla.

Jej posledná šanca, ako sa vyhnúť upratovaniu je skryť sa. V poslednej chvíli, keď už počula otvorenie dverí, sa konečne niekam rýchlo zahrabala a dúfala, že s týmto kúskom T2-ky sa už hýbať nebude.

Plány ostatných vedúcich sa ale nečakane zmenili, lebo namiesto presúvania nábytku si sadli a rozprávali sa. Avšak Kika o sebe nemôže dať vedieť, lebo keby sa dozvedeli, prečo sa skrývala, mohlo by to mať nejaké prerábkové následky. Tak si povedala, že si zatiaľ skúsi premyslieť, kde inde sa ešte mohla skryť tak, aby ju žiadny vedúci nemohol nájsť ani keď sa bude obzerať okolo seba.

Úloha

Na vstupe dostanete plán T2-ky v podobe mriežky rozmerov \(m\times n\), kde je vyznačená poloha každého vedúceho a všetkých stien, skríň a iných rôznych prekážok, ktoré obmedzujú výhľad ostatných vedúcich. Vašou úlohou je zrátať všetky miesta v T2-ke, na ktoré nevidí ani jeden z vedúcich (pri ľubovoľnom otočení hlavy – dozadu, dopredu, doľava, doprava, ale nie diagonálne) a Kika sa tam vie potenciálne skryť.

Formát vstupu

V prvom riadku vstupu dostanete dve čísla \(n\) a \(m\) – výšku a šírku plánu T2ky. Nasleduje \(n\) riadkov, na každom je \(m\) znakov kde . reprezentuje priechodné miesto, # prekážku a V vedúceho.

Formát výstupu

Na výstup vypíšte jedno číslo – počet políčok, ktoré nie sú videné v ľubovoľnom momente ani jedným z vedúcich.

Príklady

Input:

4 6
V#....
.V..#.
..#V..
......

Output:

7

Input:

3 3
.#.
#V#
.#.

Output:

4


  1. T2-ka je miestosť KSPákov na Matfyze. Pre bližšie predstavenie si tejto miestnosti – sú v nej skrine, gauče, stoly a veľká kopa eráru.↩︎

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.