LatticeLand#3574
LeaperLad, LatticeLand-də lava gölünün üstündə asılmış bir diskdə oyanır. O, disklərdən birində HeloPak-ını görür və bununla bu təhlükəli tələdən qaça biləcəyini bilir.
Disklər bir-birindən çox uzaqdır; bir az impuls olmadan yalnız dərhal bitişik diskə tullanmaq mümkündür. Tullanış üçün sürət qazandıqdan sonra, toxunduğu hər diskdə sürətini artırmaq olar.
Disklər düzbucaqlı bir şəbəkədə yerləşir, hər şəbəkə nöqtəsində bir disk var. Hər diskdə üfüqi və ya şaquli istiqamətdə sürətini bir vahid artırmaq və ya azaltmaq (amma eyni diskdə hər ikisini deyil) mümkündür. Alternativ olaraq, bir diskə addım atarkən sürətini saxlaya bilər. Beləliklə, düz xətt boyunca, durğun vəziyyətdən başlayaraq, bir vahid, sonra iki vahid, sonra üç, sonra iki, sonra bir tullanış edə bilər.
Bəzi disk cütləri arasında toxunmamalı olduğu od divarları var. Bu divarlardan birinə istənilən qədər yaxınlaşa bilər, amma toxunmamalıdır. Şəbəkənin kənarından da düşə bilməz.
LeaperLad HeloPak-ına çatıb o diskdə dayanmaq üçün nə qədər tez hərəkət edə bilər?
Girişdə hər sətirdə bir problem olacaq. Giriş sətri bir-birindən bir boşluqla ayrılmış bir sıra tam ədədlərdən ibarət olacaq.
İlk iki tam ədəd w və h, şəbəkənin eni və hündürlüyü olacaq. Bu dəyərlərin hər biri 1 ilə 64 arasında, daxil olmaqla, olacaq. Bundan sonra LeaperLad-ın oyandığı diskin koordinatlarını təmsil edən iki tam ədəd gələcək. Bundan sonra HeloPak-ın olduğu diskin koordinatlarını təmsil edən iki tam ədəd gələcək. Növbəti tam ədəd f, od divarlarının sayını göstərəcək. Altı və ya daha az od divarı olacaq. Bundan sonra f dəst 4 tam ədəd gələcək, divarların uclarının koordinatlarını təmsil edəcək.
Bütün koordinatlar üçün ilk ədəd 0 ilə w−1 arasında, daxil olmaqla, və ikinci ədəd 0 ilə h−1 arasında, daxil olmaqla, olacaq. Bütün od divarları ən azı bir vahid uzunluğunda olacaq. HeloPak və LeaperLad heç vaxt eyni diskdə başlamayacaq, nə də hər hansı biri od divarında olan bir diskdə başlamayacaq. LeaperLad-ın HeloPak-ına çatması üçün həmişə bir yol olacaq.
Ən çox 50 problem olacaq.
Hər giriş sətri üçün, LeaperLad-ın HeloPak-ına çatması üçün lazım olan minimal hərəkət sayını göstərən bir tam ədəd çap edin. İlk bir neçə nümunəyə diqqətlə baxın; hərəkətlərin necə sayıldığını aydınlaşdırır.
Nümunələr
Nümunə 1
2 1 0 0 1 0 0
Bu iki hərəkət tələb edir. İlk hərəkətdə, LeaperLad müsbət x istiqamətində bir vahid sürətlənir və təyinat diskə atılır. İkinci hərəkətdə, tələb olunan sıfır sürətə qədər yavaşlayır (nəzərə alın ki, LeaperLad-ın mövqeyi ikinci hərəkət zamanı dəyişməsə də, bu, ümumi sayına daxil edilir).
Nümunə 2
2 2 0 0 1 1 0
Bu dörd hərəkət tələb edir. LeaperLad əvvəlki nümunədə olduğu kimi sağa hərəkət edir, amma əvvəlcə x istiqamətində yavaşlamalı, sonra aşağı tullanmaq üçün y istiqamətində sürətlənməlidir, sonra yenidən hərəkətsiz olmaq üçün yavaşlamalıdır.
Nümunə 3
4 2 1 0 2 1 2 0 1 1 1 2 0 3 0
Bu səkkiz hərəkət tələb edir. LeaperLad durğun vəziyyətdən diaqonal tullanış edə bilməz; əvvəlcə bir az sürət qazanmaq üçün geri dönməlidir. Beləliklə, əvvəlcə (0, 0) mövqeyinə hərəkət etməlidir, sonra dönmək üçün yavaşlamalı, sonra x istiqamətində sürətlənərək öz ilkin yerinə tullanmalıdır. Onun impulsu ona diaqonal hərəkət etmək üçün y istiqamətində sürətlənməyə imkan verir. Təyinat yerinə endikdən sonra, həm x, həm də y istiqamətlərində bir vahid impulsu var, buna görə də yavaşlamalıdır, əvvəlcə y istiqamətində (bu onu təyinat yerini keçərək (3, 1) mövqeyinə aparır). Sonra dönmək üçün yavaşlayır, bir daha təyinat yerinə tullanır və sonra hərəkətsiz olmaq üçün yavaşlayır, ümumilikdə səkkiz hərəkət.
Nümunə 4
9 9 8 3 8 5 4 8 4 5 1 5 1 2 4 2 4 5 7 5 7 8 4
Bu 16 hərəkət tələb edir.
Nümunə 5
9 9 2 2 7 8 6 0 6 4 3 6 8 3 7 1 7 4 1 3 6 7 0 4 1 1 2 5 7 6 3
Bu 43 hərəkət tələb edir.
Nümunə 1