Začnime tým, že si uvedomíme, čo je našou úlohou. Sklad nám predstavuje mriežkové bludisko, v ktorom je každé políčko buď priechodné (prázdne) alebo je stenou (je tam polica). Snažíme sa dostať na políčko X, pričom nevieme kde sa nachádza. Vždy vieme čo je pred nami, vpravo a vľavo.

Držanie sa steny

Jeden zo spôsobov, ktorým to môžeme spraviť je, že sa vždy budeme držať jednej zo stien. V tomto riešení si zvolíme, źe sa budeme držať pravej steny. To znamená, že ak bude dať, vždy pôjdeme doprava. Ak nie, pôjdeme dopredu a ak ani to nebude možné, pôjdeme doľava. Ak nevieme ísť ani do ľava, budeme vedieť, že sme sa dostali do slepej uličky a otočíme sa naspäť.

Toto riešenie by fungovalo v sadách 1 a 3, ale v sadoch 2 a 4 by sme sa narazili na problém tohto riešenia. V týchto sadách sa totiž môžu nachádzať cykly prázdnych políčok, v ktorých by sme sa zasekli. Napr. v takomto bludisku, by sme sa touto taktikou nikdy do cieľa nedostali:

Pamätanie si kde sme boli

Tento problém vieme vyriešiť jednoducho tak, že si budeme pamätať, kde sme už boli. Keď sa budeme rozhodovať, kadiaľ chceme ísť, budeme pri tom uvažovať aj o tom, či sme už niekde boli. Ak sme na danom políćku už raz boli, nechceme tam ísť znovu, lebo tým smerom sme už bludisko prehľadali a cieľ sme nenašli. Ak sa ocitneme na mieste, z ktorého sme už išli každým smerom, vrátime sa naspäť smerom, z ktorého sme prišli.

Vrátenie sa naspäť vieme docieliť viacerými spôsobomi, napr. týmito: - Pre každé políčko si budeme pamätať, odkiaľ (resp. z ktorého smeru) sme sa naň prvý krát dostali. - Pre kaďé políčko si budeme pamätať, koľké v poradí sme ho navštívili. Keď nebudeme mať do žiadnej strany voľný smer, pôjdeme na susediace políčko s čo najmenším poradovým číslom. - Pohyb budeme implementovať rekurzívne a pri skončení rekurzívneho volania sa vrátime naspäť.

V tomto riešení budeme implementovať prvú možnosť ale ľubovolná z týchto možností vie fungovať.

Implementácia

Implementáciu začneme globálnymi premennými, ktoré budeme potrebovať. Okrem nich si zadefinujeme aj konštantný zoznam smerov vo forme (dr, dc), kde dr je posun v riadku a dc je posun v stĺpci.

Odkiaľ sme prišli a kde sme už boli si môžeme pamätať v dvojrozmernom poli alebo pomocou štruktúr dict a set. Aby sme sa nemuseli trápiť s definíciami a indexovaním dvojrozmerného poľa, použijeme radšej dict a set.

SMERY = [
    (0, -1),  # dole
    (-1, 0),  # vlavo
    (0, 1),   # hore
    (1, 0)    # vpravo
]

R, C = list(map(int, input().split()))
r, c = list(map(int, input().split()))

odkial = dict()
navstivene = set()
smer = 0  # Zaciname smerujuc nadol

Teraz si môžeme zadefinovať pomocné funkcie, aby sme nemuseli zbytočne opakovať veľa kódu. Smery, ktoré sme definovali sú zoradené tak, že ďalší smer v poradí je vždy doprava a predchádzajúci je vždy doľava. Otáčanie si tým vieme zjednodušiť na pripočítavanie a odčítavanie 1 z aktuálneho smeru. Nesmieme ale zabudnúť na použite modula 4, aby náš smer vždy zostal v intervale 0-3.

def vlavo_s():
    return (r + SMERY[(smer+3)%4][0], c + SMERY[(smer+3)%4][1])

def vpred_s():
    return (r + SMERY[smer][0], c + SMERY[smer][1])

def vpravo_s():
    return (r + SMERY[(smer+1)%4][0], c + SMERY[(smer+1)%4][1])


def nacitaj():
    # trojica (vlavo, vpred, vpravo)
    return input().split()

def krok(kam):
    global r, c, smer
    print(kam, flush=True)
    if kam == 'L':
        smer = (smer+3)%4
    elif kam == 'R':
        smer = (smer+1)%4
    else:
        nr, nc = r + SMERY[smer][0], c + SMERY[smer][1]
        if (nr, nc) not in odkial:
            # odkial chceme nastavit iba pri prvom navstiveni
            odkial[(nr, nc)] = (r, c)
        r, c = nr, nc

Teraz sa dostávame k najdôležitejšej časti programu. Začnime tým, že urobíme prvú časť programu, ktorá sa bude snažiť držať pravej steny. Ak je políčko vpravo priechodné a ešte sme na ňom neboli, pôjdeme tam. Ak nie, pôjdeme dopredu (samozrejme, iba ak sme tam ešte neboli) alebo ak ani to nie je možné, pôjdeme doľava. Ak ani to nie je možné, vrátime sa naspäť odkiaľ sme prišli.

Celý program dáme do slučky, ktorá sa bude vykonávať, pokiaľ sa nedostaneme do cieľa.

while True:
    navstivene.add((r, c))
    vlavo, vpred, vpravo = nacitaj()

    if vpravo == '.' and (vpravo_s()[0], vpravo_s()[1]) not in navstivene:
        # pri otocke nas netrapi co je pri nas, cize odpoved nacitame ale zahodime
        krok('P'); nacitaj()
        krok('K')
    elif vpred == '.' and (vpred_s()[0], vpred_s()[1]) not in navstivene:
        krok('K')
    elif vlavo == '.' and (vlavo_s()[0], vlavo_s()[1]) not in navstivene:
        krok('L'); nacitaj()
        krok('K')
    else:
        naspat = odkial[(r, c)]
        dr, dc = naspat[0] - r, naspat[1] - c
        # zistime, ktorym smerom sa potrebujeme otocit, otocime sa a urobime krok
        potrebny_smer = SMERY.index((dr, dc))
        for i in range((smer - potrebny_smer)%4):
            krok('R'); nacitaj()
        krok('K')

V tomto kóde ešte nikde nekontrolujeme, či sa pri nás nachádza cieľ. Kontrolu na to umiestnime pred zvyšok rozhodovacieho kódu, keďže ak sme pri cieli chceme ísť priamo k nemu a netrápi nás zvyšok kódu. Keď sme sa tam už presunuli, môžeme ukončiť slučku.

while True:
    navstivene.add((r, c))
    vlavo, vpred, vpravo = nacitaj()

    if vpravo == 'X':
        krok('P'); nacitaj()
        krok('K')
        break
    elif vpred == 'X':
        krok('K')
        break
    elif vlavo == 'X':
        krok('L'); nacitaj()
        krok('K')
        break

    ...