Lənətlənmiş Qəbiristanlıq
Bu axşam Halloween gecəsidir və Qorxaq John və dostları bu hadisəni qeyd etmək üçün əyləncəli bir şey etməyə qərar veriblər: qəbiristanlığı keçmək. Qorxaq John bunu heç də əyləncəli hesab etməsə də, nəhayət, onların macərasına qoşulmağa razılaşıb. Girişdə olduqda, dostlar bir-bir qəbiristanlığı keçməyə başlayıblar və indi Qorxaq Johnun növbəsidir. O, hələ də nənəsinin ona uşaq ikən danışdığı hekayələri xatırlayır. Nənəsi ona Halloween gecəsi qəbiristanlıqda "lənətli dəliklər"in peyda olduğunu söyləyib. Bunlar adi dəliklər deyil, içərisinə düşən insanları qəbiristanlığın hər hansı bir nöqtəsinə, bəlkə də uzaq bir yerə aparır. Amma bu dəliklərin ən qorxunc xüsusiyyəti odur ki, onlar insanın həm məkan, həm də zaman içində səyahət etməsinə imkan verir; yəni, əgər siz "lənətli dəlik"ə düşsəniz, paralel bir kainatda, bizimkindən başqa, qəbiristanlığın hər hansı bir yerində müəyyən bir vaxt əvvəl (və ya sonra) peyda olursunuz.
Qəbiristanlıq W × H hüceyrələrindən ibarət bir şəbəkə kimi təşkil olunub, giriş (0, 0) mövqeyindəki hüceyrədə və çıxış (W − 1, H − 1) mövqeyindədir. Qorxaq John qaranlığa baxmayaraq həmişə çıxışı tanıya bilir və ora çatdığı anda qəbiristanlığa bir daha ayaq basmamaq qərarına gəlib. Çıxışa gedərkən, o, bir hüceyrədən qonşu bir hüceyrəyə keçə bilər və yalnız Şimal, Şərq, Cənub və ya Qərbə doğru gedə bilər. Hər bir hüceyrədə ya bir məzar daşı, ya bir "lənətli dəlik", ya da ot ola bilər:
• Əgər hüceyrədə məzar daşı varsa, onun üzərindən keçə bilməzsiniz, çünki məzar daşları çox hündürdür.
• Əgər hüceyrədə "lənətli dəlik" varsa və onun üzərindən keçsəniz, qəbiristanlığın hər hansı bir yerində, bəlkə də fərqli bir zamanda peyda olacaqsınız. Zaman fərqi düşdüyünüz xüsusi "lənətli dəlik"dən asılıdır və müsbət, mənfi və ya sıfır ola bilər.
• Əks halda, hüceyrədə yalnız ot var və onun üzərindən sərbəst keçə bilərsiniz.
O, dəhşət içindədir, buna görə də qəbiristanlığı mümkün qədər tez keçmək istəyir. Və bu səbəbdən o, məşhur bir proqramçı olan sizə zəng edib. O istəyir ki, qəbiristanlığın təsviri verildikdə, girişdən çıxışa getmək üçün lazım olan minimum vaxtı hesablayan bir proqram yazasınız. Qorxaq John "lənətli dəliklər"dən istifadə etməyə razıdır, əgər onlar ona qəbiristanlığı daha tez keçməyə imkan verirsə, amma o, dəliklərdən istifadə edərək sonsuz şəkildə keçmişə səyahət etmək və itmək ehtimalından ölümdən qorxur, buna görə də proqramınız bu vəziyyətləri bildirməlidir.
Yuxarıdakı şəkil mümkün bir qəbiristanlığı (nümunə girişdən ikinci test halı) təsvir edir. Bu halda (2, 1) və (3, 1) hüceyrələrində iki məzar daşı və (3, 0) hüceyrəsindən (2, 2) hüceyrəsinə 0 saniyəlik zaman fərqi ilə bir "lənətli dəlik" var. Qəbiristanlığı keçmək üçün minimum vaxt 4 saniyədir, bu yol üzrə:
(0, 0) → Şərq 1 san (1, 0) → Şərq 1 san (2, 0) → Şərq 1 san (3, 0) → dəlik 0 san (2, 2) → Şərq 1 san (3, 2)
Əgər "lənətli dəlik"dən istifadə etməsəniz, ən azı 5 saniyə lazımdır.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər bir test halı iki tam ədəd W və H (1 ≤ W, H ≤ 30) ilə başlayan bir sətirdən ibarətdir. Bu tam ədədlər qəbiristanlığın eni W və hündürlüyü H göstərir. Növbəti sətir qəbiristanlıqda olan məzar daşlarının sayını göstərən bir tam ədəd G (G ≥ 0) ehtiva edir və G sətir ilə davam edir, hər biri məzar daşlarının mövqelərini ehtiva edir. Hər bir mövqe iki tam ədəd X və Y (0 ≤ X < W və 0 ≤ Y < H) ilə verilir.
Növbəti sətir "lənətli dəliklər"in sayını göstərən bir tam ədəd E (E ≥ 0) ehtiva edir və E sətir ilə davam edir. Hər biri beş tam ədəd X1, Y1, X2, Y2, T ehtiva edir. (X1, Y1) "lənətli dəlik"in mövqeyidir (0 ≤ X1 < W və 0 ≤ Y1 < H). (X2, Y2) "lənətli dəlik"in təyinat nöqtəsidir (0 ≤ X2 < W və 0 ≤ Y2 < H). Qeyd edək ki, "lənətli dəlik"in mənşəyi və təyinatı eyni ola bilər. T (−10 000 ≤ T ≤ 10 000) "lənətli dəlik"ə daxil olan an ilə təyinat nöqtəsinə çatdığı an arasındakı zaman fərqidir; müsbət rəqəm, dəliyə girdikdən sonra təyinat nöqtəsinə çatdığını göstərir. Təhlükəsiz şəkildə qəbul edə bilərsiniz ki, eyni mənşəyə malik iki "lənətli dəlik" yoxdur və "lənətli dəlik"in təyinat hüceyrəsi məzar daşı ehtiva etmir. Bundan əlavə, (0,0) və (W-1,H-1) mövqelərində nə məzar daşları, nə də "lənətli dəliklər" yoxdur.
Giriş 0 0 ehtiva edən bir sətir ilə bitəcək, bu işlənməməlidir.
Çıxış verilənləri
Hər bir test halı üçün, əgər Qorxaq Johnun sonsuz şəkildə keçmişə səyahət etməsi mümkündürsə, Heç vaxt çıxış edin. Əks halda, əgər çıxışa çatmaq mümkündürsə, girişdən çıxışa keçmək üçün lazım olan minimum vaxtı saniyələrlə yazın və əks halda Mümkün deyil çıxış edin.