Jill və Phil`in Palindromik Səyahətləri#6010
Jill və dostu Phil Varşava ətrafında velosiped sürərək "turist işi" ilə məşğul olacaqlar, yəni görməli yerləri ziyarət edəcəklər. Varşava ilə tanış olmadıqları üçün yadda saxlamaq asan olan marşrutlarla səyahət etməyi planlaşdırırlar. Səyahətləri zamanı qarşılaşdıqları hər bir kəsişmədə dörd yol olacaq: şimal, şərq, cənub və qərb istiqamətində. Onlar kəsişməyə daxil olduqları yoldan nisbətən sol (L), sağ (R) və ya irəli (F) olan yolla kəsişmədən çıxacaqlar. Heç bir kəsişmədən iki dəfədən çox keçməyəcəklər. Onların marşrutunu təsvir edən hərflər ardıcıllığı (F, L, R) palindrom təşkil edir!
Məsələn, xəritədə göstərilən marşrutu nəzərdən keçirin, şimal xəritənin yuxarısında yerləşir. Nömrələnmiş dairələrin hər biri bir kəsişməni təmsil edir; hər biri dörd yolla birləşir, baxmayaraq ki, bəziləri 3-dən şərqə gedən yol kimi ola bilər – dalan. "x" ilə işarələnmiş dairə Jill və Phil-in otelidir, bütün marşrutları irəli gedərək başlayacaq. Dairələr arasındakı xətlər (kənarlar) yolları təmsil edir.
Otelə bir palindromik marşrut FLRLF kimi göstərilə bilər: oteldən 3-ə irəli, sonra 3-dən 2-yə sola, sonra 2-dən 1-ə sağa, sonra 1-dən 3-ə sola və nəhayət 3-dən otelə irəli. Bu marşrut xəritədə yönləndirilmiş kənarlarla göstərilmişdir. Başqa bir palindromik marşrut FLLFFLLF dir. Bu marşrut oteldən 3, 2, 4, yenidən 4, 2, 1, 3 və nəhayət otelə qayıdır.
Bir xəritə verildikdə, Jill və Phil-in gedə biləcəyi bütün palindromik marşrutları tapın.
Giriş bir neçə xəritədən ibarətdir, ardınca tək sıfır olan bir sətir gəlir.
Hər bir xəritə üçün girişin ilk sətri kəsişmələrin sayını, N, verir ki, bu da 15-dən böyük olmayacaq. Sətir sonra oteldən irəli gedən yolun Jill və Phil-i aparacağı kompas nöqtəsini ('N', 'E', 'S' və ya 'W') dərhal izləyən kəsişmə nömrəsini (1..N) ehtiva edir.
Sonra N sətir var, hər biri 1 ilə N arasında nömrələnmiş bir kəsişmə üçün. Bu sətirlərin K-ci sətirindəki dörd boşluqla ayrılmış sahə, K kəsişməsindən çıxan dörd yolun hansı kəsişmələrə bağlandığını göstərir; sahələr K kəsişməsindən çıxan yolların şimal, şərq, cənub və qərb istiqamətindəki yollarına uyğun gəlir. Hər bir sahə aşağıdakılardan birini ehtiva edir:
kəsişmə nömrəsi L, dərhal ardınca böyük hərf kompas nöqtəsi 'N', 'E', 'S' və ya 'W'; bu, K kəsişməsindən çıxan müvafiq yolun göstərilən kompas nöqtəsində L kəsişməsinə bağlandığını göstərir.
0; bu, müvafiq yolun səyahət üçün mümkün olmayan dalan olduğunu göstərir.
–1; bu, otelə aparan yolu işarələyir. Xəritədə yalnız bir belə yol olacaq.
Hər bir giriş xəritəsi üçün xəritə nömrəsini və mümkün palindromik marşrutların hər birini leksikoqrafik ardıcıllıqla göstərin. Əgər mümkün palindromik marşrutlar yoxdursa, "NO ROUTES" mesajını göstərin. Nümunə çıxış formatına əməl edin.
Nümunə 1