Yük Daşıma
Nöqtə A-dan nöqtə B-yə yük daşımaq kimi sadə görünən bir vəzifə bəzən çox çətin ola bilər! GPS sistemləri marşrutları tapmaqda çox faydalı ola bilər, lakin adətən hər şeyi nəzərə almırlar. Məsələn, ən sürətli marşrutu taparkən, onlar işıqforlarda gözləməyi nəzərə alırlarmı? Tıxaclar necə? Bəlkə daha üstün proqram təminatı yaza bilərsiniz? Bu məsələdə sizə yollar, nömrələnmiş kəsişmələr (işıqforlarla) və iki anbarı olan bir küçə xəritəsi veriləcək. Sizin vəzifəniz yük maşınını anbar A-dan anbar B-yə sürmək üçün ən sürətli marşrutu tapmaqdır. Küçə xəritələri həmişə bir şəbəkə üzərində çəkilir və belə görünür: şəkilə baxın. Bu xəritədə yaxınlıq şimal, cənub, şərq və ya qərb qonşuluğu kimi müəyyən edilir. Xəritədə yalnız aşağıdakı simvollar görünür: • # simvolu yük maşınlarının hərəkət edə biləcəyi yol hüceyrəsini göstərir. Yollar ən çox iki digər yol, kəsişmə və ya anbar hüceyrəsinə bitişikdir. • Tək rəqəm [0-9] işıqforla idarə olunan kəsişməni göstərir. Kəsişmələr ən azı üç yol hüceyrəsinə bitişikdir. Kəsişmələr ardıcıl olaraq unikal nömrələnir: xəritədə ondan kiçik olan bütün qeyri-mənfi tam ədədlər görünmədikcə heç bir nömrə görünməyəcək. İşıqforların davranışı aşağıda təsvir ediləcək. • Dəqiq bir A simvolu yük maşınlarınızın başladığı anbarın yerini göstərir. • Dəqiq bir B simvolu yükünüzü göndərmək istədiyiniz anbarın yerini göstərir. • . simvolu sadəcə otdur. Bunların üzərində hərəkət edə bilməzsiniz. Sizdə anbar A-dan başlayan bir yük maşını var və aşağıdakı qaydalara uyğun olaraq onu anbar B-yə sürməyə çalışırsınız. Sadəlik üçün vaxtı atomik vahidlərə və ya növbələrə ayıra bilərik. • Bir növbədə yük maşınını bitişik yol, kəsişmə və ya anbar hüceyrəsinə köçürə və ya sadəcə eyni hüceyrədə qala bilərsiniz. • Yük maşını yalnız həmin növbədə daxil olduğu istiqamətdə kəsişmə üçün işıqfor yaşıl olduqda kəsişmə hüceyrəsinə daxil ola bilər. Bununla belə, kəsişmə hüceyrəsində olan yük maşını istənilən vaxt istənilən istiqamətdə çıxa bilər. İşıqforlu kəsişmələr dövri olaraq ya şərq-qərb, ya da şimal-cənub trafik axınına icazə verir, lakin eyni zamanda hər ikisinə icazə vermir. Onlar ilkin istiqamət və müvafiq olaraq şərq-qərb və şimal-cənub dövrlərini göstərən iki rəqəmlə təsvir edilir. Məsələn, şimal-cənub istiqamətində ilkin olaraq yaşıl olan "2 3" ilə təsvir edilən kəsişmə 1-dən 3-ə qədər olan növbələrdə şimal və cənub istiqamətində yaşıl işıq olacaq, 4-dən 5-ə qədər olan növbələrdə şərq və qərb istiqamətində, və yenidən 6-dan 8-ə qədər olan növbələrdə şimal və cənub istiqamətində, və s.
Giriş verilənləri
Giriş test faylı bir neçə halı ehtiva edəcək. Hər bir test halı boşluqlarla ayrılmış iki tam ədəd, m və n olan tək bir sətirlə başlayır. Küçə xəritəsi m sətirdən (şərq-qərb) və n sütundan (şimal-cənub) ibarət şəbəkə hüceyrələrindən (2 <= m, n <= 20) ibarətdir. Növbəti m sətir xəritəni yuxarıda problem bəyanatında müəyyən edilmiş simvolları istifadə edərək təsvir edən n simvolu ehtiva edir. Xəritədə görünən hər bir nömrələnmiş kəsişmə üçün, 0-dan başlayaraq artan qaydada, kəsişmə nömrəsi və ya '-' və ya '|' simvolu və iki tam ədəd, ai və bi (1 <= ai, bi <= 100), müvafiq olaraq şərq-qərb və şimal-cənub dövrlərinin müddətini göstərən bir mətn sətiri olacaq. '-' simvolu işıqforun ilkin olaraq şərq-qərb istiqamətində yaşıl olduğunu göstərir, '|' simvolu isə ilkin olaraq şimal-cənub istiqamətində yaşıl olduğunu göstərir. Giriş test hallarını ayıran boş bir sətir var, aşağıdakı nümunə girişdə göründüyü kimi. "0 0" rəqəmləri ilə tək bir sətir girişin sonunu göstərir; bu halı emal etməyin. Çıxış
Hər bir test halı üçün proqramınız bir sətirdə bir tam ədəd çap etməlidir: yük maşınını anbar A-dan anbar B-yə sürmək üçün lazım olan minimum növbə sayı. Əgər anbar B-yə çatmaq mümkün deyilsə, tək bir söz "impossible" çap edin.
(İkinci nümunədə, əslində aşağı marşrutla getmək yuxarıdan daha sürətlidir. Lakin, yük maşınınız 2 kəsişməsində qərbdə gözləməlidir ki, 7-ci növbədə işıq yaşıl olduqda daxil ola bilsin, sonra 10-cu növbədə 0 kəsişməsinə çatsın, 1 kəsişməsinin qərbində yenidən 14-cü növbəyə qədər gözləsin və nəhayət 17-ci növbənin sonunda anbar B-yə daxil olsun).