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

  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.↩︎

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.

n, m = map(int, input().split())

pole = [list(input()) for i in range(n)]

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
            pole[i][s] = "S"
        # dolava
        for i in range(r - 1, -1, -1):
            if pole[i][s] == "#" or pole[i][s] == "V":
                break
            pole[i][s] = "S"
        # dole
        for j in range(s + 1, m):
            if pole[r][j] == "#" or pole[r][j] == "V":
                break
            pole[r][j] = "S"
        # hore
        for j in range(s - 1, -1, -1):
            if pole[r][j] == "#" or pole[r][j] == "V":
                break
            pole[r][j] = "S"

ans = 0
for i in range(n):
    for j in range(m):
        if pole[i][j] == ".":
            ans += 1

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)\).

n, m = map(int, input().split())

pole = [list(input()) for i in range(n)]

# z lava doprava
for i in range(n):
    pozera = False
    for j in range(m):
        if pole[i][j] == "#":
            pozera = False
        if pole[i][j] == ".":
            if pozera:
                pole[i][j] = "S"
        if pole[i][j] == "V":
            pozera = True

# z prava doľava
for i in range(n):
    pozera = False
    for j in range(m - 1, -1, -1):
        if pole[i][j] == "#":
            pozera = False
        if pole[i][j] == ".":
            if pozera:
                pole[i][j] = "S"
        if pole[i][j] == "V":
            pozera = True

# z hora dole
for j in range(m):
    pozera = False
    for i in range(n):
        if pole[i][j] == "#":
            pozera = False
        if pole[i][j] == ".":
            if pozera:
                pole[i][j] = "S"
        if pole[i][j] == "V":
            pozera = True

# z dola hore
for j in range(m):
    pozera = False
    for i in range(n - 1, -1, -1):
        if pole[i][j] == "#":
            pozera = False
        if pole[i][j] == ".":
            if pozera:
                pole[i][j] = "S"
        if pole[i][j] == "V":
            pozera = True

ans = 0
for i in range(n):
    for j in range(m):
        if pole[i][j] == ".":
            ans += 1

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