Meşə

Orta zolaqda bəzən meşə bitir. Meşəni faydalı əkin sahələrindən ayırmaq üçün meşə ilə sahə arasında hasar tikilmişdir. Lakin zaman keçdikcə meşə böyüyür və hasarı köçürmək lazımdır.

Ərazini N×M ölçülü hüceyrələrdən ibarət xəritə şəklində təqdim etmək olar. Hər bir hüceyrə ya meşə, ya sahə, ya da hasar ehtiva edir. Hasar ehtiva edən hüceyrələr aşağıdakı xüsusiyyətlərə malikdir:

1. Hasar əlaqəlidir. Bu o deməkdir ki, hər bir hüceyrədən digərinə yalnız qonşu hüceyrələr vasitəsilə keçmək mümkündür (qonşu hüceyrələr ortaq tərəfi olan hüceyrələr hesab olunur).

2. Hasar daxil edilmə baxımından minimaldır, yəni hasardan hər hansı bir hüceyrəni çıxarsaq (onu meşə və ya sahə ilə əvəz etsək), o, artıq hasar olmayacaq.

3. Hasar meşəni və sahəni ayırır, yəni hasarın solundakı bütün hüceyrələr meşə, sağındakı bütün hüceyrələr isə sahədir.

4. Hasarı elə bir hüceyrə ardıcıllığı şəklində təqdim etmək olar ki, növbəti hüceyrə əvvəlkindən solda, sağda və ya aşağıda yerləşir.

Sizə hasar üçün əvvəlcə tutduğu bütün hüceyrələrdən, həmçinin hasarın ilkin hüceyrələrindən sağda bir hüceyrədən çox olmayan hüceyrələrdən istifadə etməyə icazə verilir (xəritənin sol və sağ sütunlarından istifadə etmək qadağandır). Sizin vəzifəniz yuxarıda göstərilən hasar şərtlərinə cavab verən minimal uzunluqda hasar qurmaqdır. Məlumdur ki, ilkin hasar hasardır, həmçinin xəritənin sol sütunu tamamilə meşə, sağ sütunu isə tamamilə sahə ilə doludur.