Santa Claus — 2022-03-12 13:23 (299 days ago) — edit — reply
Nebýt stráže, spustíme BFS. Když přidáme stráž, můžeme taky jednoduše spustit BFS, ale každý stav nyní popisuje nejen pozice hráče, ale také pozice strážce. Hráč má obecně $M \times N - 2$ možných pozic, strážce má L různých pozic, ale lze nahlédnout, že jeho stav také zahrnuje směr, kterým jde, celkem $(L-2)\times 2 = 2L - 4$ stavů (na koncových bodech směr nemá). Celkově je počet stavů lineárně asymptoticky úměrný k součinu $LMN$. Spustíme tedy BFS. Jeho časová asymptotická složitost bude dána počtem možných stavů. $O(LMN)$. Nalezená cesta bude nejkratší, stejně jako bez strážce. Kdyby existovala kratší než nalezená cesta, byla by nalezena dříve... Formálně mezi stavy úlohy se strážcem či bez není rozdíl.