Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WZP09_1B - Formuła 1

Formuła 1 to niezwykle emocjonujący sport, którym w Polsce interesuje się coraz więcej osób. Po ostatnich sukcesach Roberta Kubicy władze stolicy postanowiły, że w przyszłym sezonie jeden z wyścigów musi się odbyć w Warszawie. Jako, że budowa toru wymaga ogromnych nakładów finansowych postanowiono, iż będzie to wyścig uliczny. Ze względu na stan warszawskich dróg, po których z trudem poruszają się samochody terenowe, na specjalnym posiedzeniu wyznaczono fragmenty poszczególnych ulic, które po niewielkich remontach nadawałyby się do poprowadzenia przez nie toru. Niestety żaden z urzędników nie zadał sobie trudu żeby sprawdzić czy wybrane ulice w ogóle tworzą pętle.

Jak zwykle zadanie to powierzono Tobie. Mając dostępne mapy wybranych obszarów sprawdź czy z ulic nadających się do poprowadzenia toru da się utworzyć pętle. Mapy obszarów podzielone są na pola, każde pole oznaczone jest jedną z 5 liter:

  • T – droga nadająca się do poprowadzenia toru
  • D – zwykła droga
  • R – restauracja
  • H – hotel
  • O – inny obszar

Jak widać tor wyścigu może przebiegać tylko po polach oznaczonych literą T. Tor nie może przebiegać po przekątnej np. z pola (2,2) nie możemy poprowadzić toru do (1,1), (1,3), (3,1), (3,3). Najmniejszy z możliwych torów może się składać z czterech pól tworzących kwadrat.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna t (1 <= t <= 10) określająca ilość zestawów danych. W kolejnych liniach znajduje się t zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba naturalna n (1 <= n <= 20) określająca długość boku rozpatrywanego kwadratowego obszaru. W kolejnych n liniach zestawu danych znajduje się opis obszaru. Każda linia zawiera po n liter opisujących kolejne pola.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać TAK jeżeli z dróg nadających się do poprowadzenia toru można utworzyć pętlę albo NIE w przeciwnym wypadku.

Przykład

Dla danych:

3 
5 
OHRHR 
TTTTD 
RTOTH 
HTTTR 
ORHTH 
8 
TTTTDDDD 
HHHTRHOO 
RORTTTTD 
OOHORHTO 
DDDTHOTH 
OOOTTTTO 
HROOOOOH 
OOOOOOOO 
5 
OTTTO 
TOOOT 
TOHOT 
TOOOT 
OTTTO 

Twój program powinien wypisać:

TAK
NIE
NIE

Dodane przez:Maciej Boniecki
Data dodania:2009-10-31
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: NODEJS OBJC PERL6 SCM qobi SQLITE VB.NET
Pochodzenie:Wiosenne Zawody Programistyczne 2009

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.