Zadanie
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
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.↩︎
Riešenie tejto úlohy nie je vôbec zložité. Jediné, čo nám stačí spraviť, je prejsť celú miestnosť a zistiť pre každého vedúceho, kam vidí. Ukážeme si dva spôsoby ako to spraviť.
Prechádzanie vedúcich
Budeme sa postupne posúvať po políčkach a pozerať sa na to, či na danom políčku stojí vedúci. V prípade, že stojí, označíme si všetky políčka na ktoré vidí nad a pod ním, vľavo a vpravo od neho ako “ohrozené”. Teda všetky, ktoré nie sú už za nejakou prekážkou alebo iným vedúcim.
Keď toto spravíme pre všetkých vedúcich, tak nám na plániku ostanú neoznačené len miesta, na ktoré nevidí ani jeden vedúci. Stačí ich už len zrátať a dostaneme počet miest, na ktoré sa môže Kika bezpečne skryť.
Časová a pamäťová zložitosť
Keďže rozmery nášho plániku zo vstupu, ktorý si musíme zapamätať, sú \(m\times n\) a prechádzame iba tento plánik, tak aj časová zložitosť bude \(O(m\cdot n)\). Teraz sa možno zdá, že to nevychádza, lebo vždy, keď prídeme na vedúceho, musíme označiť všetky políčka v stĺpci a riadku, na ktoré vidí a tých môže byť až \(n+m-1\). Treba si však uvedomiť, že ak takto označíme napríklad veľkú časť jedného riadu, tak to znamená že na tom úseku nebol žiadny vedúci a teda ho následne prejdeme rýchlo. Dá sa teda povedať, že na každé políčko sa “pozeráme” najviac \(5\) krát. Raz keď kontrolujeme či je tam vedúci a potom najviac raz z každého smeru, podla toho či na to políčko z daného smeru vidí vedúci. Z toho vychádza časová zložitosť \(O(5\cdot m\cdot n)\), ale keďže \(5\) je len konštanta, tak \(O(m\cdot n)\).
Pamäťová zložitosť je \(O(m\cdot n)\), lebo si pamätáme iba plánik, ktorý v priebehu prepisujeme.
= map(int, input().split())
n, m
= [list(input()) for i in range(n)]
pole
for r in range(n):
for s in range(m):
if pole[r][s] != "V":
continue
# doprava
for i in range(r + 1, n):
if pole[i][s] == "#" or pole[i][s] == "V":
break
= "S"
pole[i][s] # dolava
for i in range(r - 1, -1, -1):
if pole[i][s] == "#" or pole[i][s] == "V":
break
= "S"
pole[i][s] # dole
for j in range(s + 1, m):
if pole[r][j] == "#" or pole[r][j] == "V":
break
= "S"
pole[r][j] # hore
for j in range(s - 1, -1, -1):
if pole[r][j] == "#" or pole[r][j] == "V":
break
= "S"
pole[r][j]
= 0
ans for i in range(n):
for j in range(m):
if pole[i][j] == ".":
+= 1
ans
print(ans)
Druhý spôsob - zametanie
Zametanie je prístup, ktorý spočíva v tom, že cez nejakú plochu (pole) prechádzame v jednom smere a ťaháme so sebou nejakú informáciu – ako keď metla ťahá špinu. My budeme zametať postupne vo všetkých \(4\) smeroch: zhora, zdola, zľava a sprava, aby sme si v plániku zaznačili, ktoré políčka sú videné nejakým vedúcim. Bližšie si popíšeme jeden z nich.
Ideme zametať zľava doprava. Môžeme si teda predstaviť že každý vedúci sa pozerá iba doprava a chceme označiť videné políčka. Po takomto zjednodušení môžeme prechádzať riadok po riadku a pamätať si len či sa niekto pozerá, alebo nie.
Nakoniec opäť prejdeme plánik a zistíme, ktoré políčka sú “neohrozené”.
Časová a pamäťová zložitosť
Na tomto riešení ešte jasnejšie vidieť, že \(4\) krát prejdeme celé pole a nerobíme pri tom nič časovo náročnejšie, ako že sa pozrieme na celý plánik, teda časová aj pamäťová zložitosť je opäť \(O(m\cdot n)\).
= map(int, input().split())
n, m
= [list(input()) for i in range(n)]
pole
# z lava doprava
for i in range(n):
= False
pozera for j in range(m):
if pole[i][j] == "#":
= False
pozera if pole[i][j] == ".":
if pozera:
= "S"
pole[i][j] if pole[i][j] == "V":
= True
pozera
# z prava doľava
for i in range(n):
= False
pozera for j in range(m - 1, -1, -1):
if pole[i][j] == "#":
= False
pozera if pole[i][j] == ".":
if pozera:
= "S"
pole[i][j] if pole[i][j] == "V":
= True
pozera
# z hora dole
for j in range(m):
= False
pozera for i in range(n):
if pole[i][j] == "#":
= False
pozera if pole[i][j] == ".":
if pozera:
= "S"
pole[i][j] if pole[i][j] == "V":
= True
pozera
# z dola hore
for j in range(m):
= False
pozera for i in range(n - 1, -1, -1):
if pole[i][j] == "#":
= False
pozera if pole[i][j] == ".":
if pozera:
= "S"
pole[i][j] if pole[i][j] == "V":
= True
pozera
= 0
ans for i in range(n):
for j in range(m):
if pole[i][j] == ".":
+= 1
ans
print(ans)
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ť.