Riešenie hrubou silou

Priamočiare riešenie, ktoré sa ponúka, je vyskúšať všetky políčka. Pre každé políčko vieme spočítať vzdialenosť, držať si doteraz najvzdialenejšie políčko, ktoré na konci vrátime. To je ale pomalé, presnejšie $O(nm)$ pomalé. Nešlo by to rýchlejšie?

Zaujímavá myšlienka

Otázka je, či vlastne naozaj potrebujeme vyskúšať všetky políčka. Rozdeľme si miestnosť na polovicu na výšku aj na šírku.

Pozrime sa na úlohu najskôr v jednom rozmere, tj. miestnosť je veľkosti $1 \cdot m$ (t. j. dlhý slíž), a predpokladajme zatiaľ, že $m$ je párne. Následne si tento slíž rozdeľme na dve polovice. Vidíme, že akonáhle je počítač v ľavej polovici, tak najďalej vieme byť na políčku najviac vpravo a opačne. Ak by sme chceli maximalizovať iba rozdiel tejto súradnice, tak nech je počítač v hocijakom riadku, my chceme ísť do opačnej polovice na kraj.

Rovnakú úvahu vieme spraviť aj pre miestnosť veľkosti $n \cdot 1$ - ak je počítač v hornej polovici, ja chcem byť v dolnej polovici a opačne.

Optimálne riešenie

Manhattanská vzdialenosť je súčet dvoch rozdielov - súradníc riadkov a súradníc stĺpcov, a tú chceme maximalizovať. Ak aplikujeme predošlú úvahu, tak vidíme, že chceme maximalizovať tieto rozdiely po zložkách, čo docielime tým, že ideme do opačných polovíc ako počítač. To nám teda dáva 4 možnosti - ak je počítač v ľavej hornej štvrtine, tak, keďže počítač je hore, tak my chceme byť v spodnom riadku, a keďže je v ľavej polovici, tak chceme byť v najpravejšom stĺpci. To spolu dáva výsledné políčko - pravý dolný roh. Rovnaká úvaha sa dá použiť pre zvyšné 3 možnosti - vrátime roh najďalej od počítača, v tomto prípade políčko $(n,m)$.

Program najskôr načíta súradnice $m$, $n$ a súradnice počítača. To, či sme v pravej/ľavej polovici nám určí súradnica počítača určujúca stĺpec. Ak je $\leq \frac{m}{2}$ (pri počítaní súradníc od $(1,1)$ ako ľavý horný roh), tak počítač je v ľavej polovici, inak je v pravej. Obdobne horná/dolná polovica, len s $n$.

Pozorný čitateľ si isto už všimol, že pri nepárnom $n$ alebo $m$ môžeme skončiť presne v strede medzi polovicami. Vtedy by sme mali dve možnosti, v zadaní ale máme garantované, že riešenie je jednoznačné a tento prípad nemôže nastať.

Ešte rýchle slovíčko k zložitostiam:

Časová zložitosť je $O(1)$, nakoľko načítanie vstupu je konštatne rýchle, vyhodnotenie polovíc a následného výsledku takisto. Pamäťová zložitosť je tiež $O(1)$, nakoľko si pamätáme iba $m$, $n$ a súradnice počítača.