Zadanie

Predstavte si dom. Velikánsky dom na kopci s ešte väčšou záhradou. Skoro až taký zámok. No, tak presne v takom dome býva Samo. Tento dom má veľa izieb a rôznych pozoruhodností vnútri aj vonku. Jednou z nich je napríklad obrovské bludisko zo živého plotu v záhrade.

Možno to znie ako z rozprávky, veľký dom, záhrada; čiže veľa zábavy. Ale Samo je jedináčik, jeho rodičia šli na týždeň na dovolenku a on ostal doma úplne sám. To už nie je taká zábava. Tak si jedného dňa pozval Marianku na návštevu.

Tú, hneď ako prišla, očarilo bludisko v záhrade. Chcela ho vyskúšať, no bála sa, že sa stratí a už sa odtiaľ nedostane. Samo jej povedal, že aj keby chodila uplne náhodne, dostane sa von v konečnom čase. To ju síce veľmi neohúrilo, no hneď nato jej navrhol, nech si vždy zapíše ktorým smerom spravila krok. Keď potom bludisko prejde, môžu si spolu z tohoto popisu zostrojiť mapku a spočítať, kolko krát Marianka spravila zlé rozhodnutie (teda išla jedným smerom, ale kratšie by to mala iným).

Marianka sa nakoniec predsalen odhodlá a vydá sa do bludiska s tým, že si bude zapisovať svoju cestu na papier. Prešiel nejaký čas, Marianka bola vonku z bludiska a spolu so Samom objavujú ďalšie pozoruhodnosti Samovho domu. Na papier s Mariankinou trasou z bludiska zabudli. Ale vás ako zvedavých čitateľov tohto príbehu zaujíma, koľkokrát Marianka v bludisku zle odbočila.

Úloha

Na vstupe dostanete popis Mariankinej cesty bludiskom. Celú mapu bludiska ale nepoznáme. O dvoch políčkach vieme že sú priechodné teda iba vtedy, ak tade Marianka niekedy prešla. Teda aj ak sú susedné, môže medzi nimi ešte byť živý plot. Vašou úlohou je na základe tohoto popisu povedať, koľkokrát Marianka zle odbočila. To znamená, koľkokrát spravila taký krok, že iným smerom by to mala bližšie do cieľa. Ak teda počas cesty napríklad prechádza cieľom, prvý krok smerom od cieľa nepovažujeme za zlý, nakoľko žiadnym iným smerom by sa ku cieľu tiež nepriblížila.

Formát vstupu

Na prvom riadku vstupu je jedno číslo \(n\) (\(1<n<10^5\)) – počet Mariankiných krokov v bludisku. Nasleduje \(n\) riadkov, kde na \(i\)–tom riadku sú súradnice \(x_i\) a \(y_i\) (\(-10^5<x_i, y_i<10^5\)), označujúce bod, na ktorý sa Marianka posunula. Pre každé po sebe idúce súradnice platí, že sa líšia v práve jednej súradnici o 1 (teda krok je jedným zo 4 smerov).

Prvé súradnice sú vždy \((0,0)\) a posledné súradnice značia cieľ.

Formát výstupu

Vypíšte jedno celé číslo – počet miest, na ktorých Marianka zle odbočila.

Príklad

Input:

7
0 0
0 1
0 2
0 1
0 0
0 -1
-1 -1

Output:

2

Prvé dva Mariankine kroky išli zlým smerom, no potom už išla priamo do cieľa.

Input:

7
0 0
-1 0
-2 0
-2 1
-1 1
-1 0
-1 -1

Output:

2

Marianka spravila koliečko. 3. a 4. krok išli zlým smerom – bližšie by bolo ísť naspäť.

Cestu, ktorou Marianka prechádza, si môžeme predstaviť ako graf. Políčka sú vrcholy a hrana je medzi nimi práve vtedy, ak medzi nimi Marianka niekedy prešla. Formát vstupu je na grafy pomerne nezvyčajný, ale stačí si uvedomiť, že táto cesta je len akýsi zoznam hrán ktoré sa môžu opakovať. Aby sa nám lepšie pracovalo, graf si potrebujeme uložiť ako zoznam susedov. Ak na to použijeme mapu, nemusíme sa ani trápiť nejakým očíslovaním vrcholov ale môžeme si ich pamätať rovno podľa súradníc.

Teraz ešte potrebujeme zistiť, ako ďaleko je ktorý vrchol od cieľa, aby sme vedeli povedať, či išla Marianka správnym smerom. Na to nám poslúži štandardné prehľadávanie do šírky.

Ako posledný krok už len prejdeme cestu tak, ako bola na vstupe a pre každý krok zistíme, či bol správnym smerom, teda či vzdialenosť od ciela je pre nasledujúce políčko najmenšia z pomedzi susedných políčok.

Časová a pamäťová zložitosť

Veľmi ľahko môžeme nahliadnuť, že jediný netriviálny cyklus v tomto riešení je BFS, o ktorom však vieme že má lineárnu zložitosť, teda aj celková časová zložitosť je \(O(n)\) od počtu krokov na vstupe. Pamäťová zložitosť je tiež \(O(n)\), pretože si potrebujeme pamätať celý vstup, a ukladáme si ho efektívne.

import queue
from collections import defaultdict

n = int(input())

cesta = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]

for _ in range(n):
    x,y = map(int, input().split())
    cesta.append((x,y))

vrcholy = set(cesta)
hrany = {}
for (x,y) in vrcholy:
    hrany[(x,y)]=[]
    
for i in range(1,n):
    hrany[cesta[i-1]].append(cesta[i])
    hrany[cesta[i]].append(cesta[i-1])

(cx,cy) = cesta[-1]
dist=defaultdict(lambda: 1000000)
q = queue.Queue()
q.put(((cx,cy),0))
while(not q.empty()):
    ((r,c), d) = q.get()
    if (r,c) in dist:
        continue
    dist[(r,c)]=d
    for s in hrany[(r,c)]:
        q.put((s,d+1))

ans=0

z= (0,0)
for u in cesta[1:]:
    m= 1000000
    for v in hrany[z]:
        m=min(m, dist[v])
    if(not dist[u]==m):
        ans+=1
    z=u

print(ans)
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>

using namespace std;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

int main(){
    vector<int>dx ={0,0,1,-1};
    vector<int>dy={1,-1,0,0};
    int n;
    cin>>n;
    vector<pair<int,int>> cesta;
    unordered_set<pair<int,int>, pair_hash> vrcholy;
    unordered_map<pair<int,int>, vector<pair<int,int>>, pair_hash> hrany;
    int a,b;
    cin>>a>>b;
    cesta.push_back({a,b});
    for(int i=1; i<n; i++){
        int a,b;
        cin>>a>>b;
        cesta.push_back({a,b});
        vrcholy.insert({a,b});
        hrany[cesta[i-1]].push_back(cesta[i]);
        hrany[cesta[i]].push_back(cesta[i-1]);
    }
    int ans=0;
    unordered_map<pair<int,int>,int, pair_hash> dist;
    queue<pair<pair<int,int>,int>> q;
    pair<int,int> c = cesta[n-1];
    q.push({c,0});

    while(!q.empty()){
        pair<pair<int,int>,int> t = q.front();
        pair<int,int> v = t.first;
        q.pop();

        if(dist.count(t.first)) continue;
        dist[t.first]=t.second;
        for (int j=0; j<hrany[v].size(); j++)
            q.push({{hrany[v][j]},t.second+1 });
    }
    for(int i=1; i<n; i++){
        int m=987654321;
        for (int j=0; j<hrany[cesta[i-1]].size(); j++)
            m=min(m, dist[hrany[cesta[i-1]][j]]);
        if(dist[cesta[i]]!=m){ans++;}
    }
    cout<<ans<<endl;
}

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