Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
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łowego | 50000B |
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 |