Finále

D: Výjezd z parkoviště

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Po úspěšném nákupu Kasiopeích triček se Pali vrací na kryté parkoviště, ale zjistil, že si nepamatuje, kam své auto zaparkoval. A protože nese hromadu triček, rozhodl se, nepůjde dovnitř, ale pomocí nového systému firmy Ricardo bude své auto ovládat zvenku k výjezdu.

Parkoviště je obdelníkového tvaru a je reprezentováno čtvercovou mřížkou, kde některá políčka jsou pro auto průjezdná a jiná ne. Pali podle mapy před parkovištěm ví, která políčka jsou neprůjezdná. Neprůjezdným políčkům říkejme pro stručnost zdi. Pali může pomocí ovladače autu přikázat, aby popojelo na jedno ze čtyř políček, které sousedí stranou s tím, na kterém zrovna je. Pokud je tam zeď, auto příkaz neposlechne a zůstane stát; je chytré a nedopustí, aby nabouralo. Celé parkoviště je ohraničené zdmi kromě jednoho políčka, které je výjezd.

Háček je v tom, že si Pali nemůže vzpomenout, kam přesně zaparkoval! Pamatuje si, že to bylo buď políčko A, nebo políčko B. Tak ho napadlo, že může autu dávat takové příkazy, aby ho z parkoviště vyvedl nezávisle na tom, jestli je na A, nebo na B. Protože už nechce celý nákup nést, chtěl by, aby auto k výjezdu přijelo co nejdříve. Pomozte mu najít co nejkratší posloupnost příkazů takovou, že se auto určitě dostane na výjezd z parkoviště, ať už je na A, nebo B. Jakmile se auto ocitne na výjezdu, Pali naloží nákup a odjede, takže stačí, aby se v průběhu provádění příkazů ocitl určitě aspoň jednou na výjezdu; jakmile ho Pali uvidí, přestane dávat příkazy.

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů.
Každý test začíná čísly N – počet řádků místnosti a M – počet jejích sloupců.
Následuje N řádků. Na každém je řetězec o M znacích, reprezentující řádek místnosti. Jeho znaky mají následující význam:

  • '.' – volné políčko
  • '#' – neprůchozí políčko
  • 'A'; 'B' – jedno z možných umístění auta (políčko je také průchozí)
Máte zaručeno, že na znaky 'A' a 'B' se na vstupu vyskytnou každý právě jednou. Také platí, že na okraji parkoviště (na prvním a posledním řádku a sloupci) jsou všude zdi kromě jednoho políčka, které je volné (nemůže na něm ani začínat auto) a reprezentuje výjezd z parkoviště, kam se má auto dostat. To je vždy možné z obou možných počátečních políček. Máte zaručeno, že řešení vždy existuje.

Tvar výstupu

Pro každý testovací vstup vypište na samostatném řádku řetězec, reprezentující posloupnost příkazů, které má Pali autu dát, aby určitě přijelo na výjezd z parkoviště. Řetězec by se měl sestávat ze znaků '^', '>', 'v', '<', reprezentující jednotlivé příkazy. Označme (i,j) políčko na i-tém řádku a v j-tém sloupci. Řekněme, že auto je zrovna na (i,j). Znaky pak mají tyto významy:

  • '^' – pohni se na (i-1,j)
  • '>' – pohni se na (i,j+1)
  • 'v' – pohni se na (i+1,j)
  • '<' – pohni se na (i,j-1)
Vypište nejkratší řetězec, který auto jistě dostane na výjezd z parkoviště. Pokud existuje více řešení, vypište libovolné z nich.

Lehká verze

  • T ≤ 10
  • Parkoviště nemá jiné zdi než ty na okraji.
  • 4 ≤ N, M ≤ 40

Těžká verze

  • T ≤ 10
  • 4 ≤ N, M ≤ 40

Ukázkový vstup

2
4 4
####
#AB#
#...
####
5 4
####
#BA#
#.##
#...
####

Ukázkový výstup

v>>
<vv>>

Vysvětlení ukázkového vstupu a výstupu

V prvním případě projede auto postupně tato políčka, pokud bylo na políčku A:

####
#1.#
#234
####
A pokud bylo na políčku B, pojede touto cestou:
####
#.1#
#.23
####
Další možné řešení by bylo ">v>".

Druhý případ by se nemohl vyskytnout v lehké verzi, protože v něm jsou i jiné zdi než ty na okraji. Trasa auta bude takováto, pokud bylo na políčku A:

####
#21#
#3##
#456
####
A pokud bylo na políčku B, navštíví postupně tato políčka:
####
#1.#
#2##
#345
####
Pokud bylo na políčku B, zůstane po prvním příkazu na svém místě, protože po něm chceme, aby se pohnulo do zdi.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)