Muzeyə Kömək Edin
Milli Muzey Kuratorları Assosiasiyası sizə maraqlı bir problem təqdim edir. Ölkə Prezidenti, ictimai imicini yaxşılaşdırmaq məqsədilə, ölkədəki müxtəlif İncəsənət Muzeylərini ziyarət etməyə qərar verib. Bununla özünü zərif bir insan kimi göstərmək istəyir. Lakin, çox məşğul olduğu və incəsənət haqqında məlumatı olmadığı üçün, ziyarətlər üçün iki məhdudiyyət qoyub:
Hər muzeydə yalnız bir rəssamın əsərlərini görmək istəyir ki, ziyarətə asanlıqla hazırlaşa bilsin və özünü incəsənət bilicisi kimi göstərə bilsin. Lakin həmin rəssamın bütün əsərlərini görməsi vacib deyil.
Vaxt itirmək istəmir və sərgini mümkün olan ən qısa yolla gəzməyi tələb edir.
Kuratorlar Prezidentin tələblərinə əməl etməyə hazırdırlar, lakin sərgidəki şah əsərləri yalnız düz bir yol əldə etmək üçün yenidən yerləşdirmək istəmirlər. Onların yeganə güzəşti, iki şah əsərin yerini müvəqqəti dəyişdirməkdir, əgər bu, daha qısa bir yol əldə etməyə kömək edərsə.
Sizdən sərginin planını qəbul edən və yuxarıdakı məhdudiyyətlərə uyğun olaraq ən qısa yolu tapan bir proqram yazmağınız tələb olunur. Tapşırığınızı asanlaşdırmaq üçün kuratorlar artıq standart bir plan müəyyən ediblər. Şəkil 1 belə bir planı göstərir.
Şəkil 1: Muzeyin Planı
Prezidentin gəzintisi həmişə sol divardan (X = 1, hər hansı Y) başlayır və sağ divarda (X = X_max, hər hansı Y) bitir. Gəzinti üfüqi və ya şaquli şəkildə edilə bilər; diaqonal hərəkətlərə icazə verilmir. Müəyyən bir rəssamın əsərləri hamısı eyni böyük hərflə (A, B, C, və s.) işarələnib. Şəkil 1-dən bir neçə hal göstərilə bilər:
Əgər prezident A rəssamının əsərlərini görmək istəyirsə, soldan sağa bir yol yoxdur. Belə bir yol, B rəssamının (6, 6)-da olan əsəri ilə A rəssamının (1, 8), (7, 8), (8, 8), (10, 6), (11, 6) və ya (11, 3)-də olan əsərlərindən biri dəyişdirilərsə əldə edilə bilər.
Əgər prezident B rəssamının əsərlərini görmək istəyirsə, artıq bir yol var, (1, 10)-da başlayıb (11, 5)-də bitir. Daha qısa bir yol, D rəssamının (11, 7)-də olan əsəri ilə B rəssamının məsələn (10, 6)-da olan əsəri dəyişdirilərsə əldə edilə bilər.
Əgər prezident C rəssamının əsərlərini görmək istəyirsə, artıq (1, 1)-dən (1, 11)-ə düz bir yol var və daha qısa bir yol əldə edilə bilməz.
Əgər prezident D, E və ya F rəssamlarının əsərlərini görmək istəyirsə, soldan sağa bir yol əldə etmək mümkün deyil.
Giriş verilənləri
Giriş faylı problemin bir neçə nümunəsini ehtiva edə bilər. Hər bir nümunə aşağıdakı formatda verilmişdir (bütün rəqəmlər müsbət tam ədədlərdir):
Birinci sətir X_max və Y_max tam ədədlərini, planın ölçülərini ehtiva edir. Siz 1 ≤ X_max,Y_max ≤ 100 olduğunu qəbul edə bilərsiniz.
İkinci sətir ziyarət ediləcək rəssamın (böyük hərflə) hərfini ehtiva edir.
Y_max sətir, hər biri X_max hərf (aralarında boşluq olmadan). Birinci giriş sətiri Y_max indeksinə, ikinci sətir Y_max-1 indeksinə və s., son sətir isə 1 indeksinə uyğundur.
İki sıfırdan ibarət bir sətir giriş faylını bitirir. Rəqəmlər boşluqlarla ayrılır.
Çıxış verilənləri
Problemin hər bir nümunəsi üçün proqramınız aşağıdakı kimi çıxış verməlidir.
Əgər bir yol varsa, proqramınız əvvəlcə "Exchange (x,y) and (u,v)" mesajını yazmalıdır, əgər dəyişiklik baş verəcəksə, ya da "No exchange" əks halda. Bundan sonra, ən qısa yol, hər koordinat bir sətirdə olmaqla yazılmalıdır. Əgər bir neçə yol ən qısadırsa, onlardan hər hansı biri yazıla bilər, lakin dəyişikliksiz bir yol dəyişikliklərlə olanlardan üstün tutulmalıdır.
Əgər bir yol yoxdursa, proqramınız yalnız "No path" mesajını yazmalıdır.
Hər bir nümunənin çıxışı boş bir sətirlə bitir.