Qnom və sikkələr
Düzbucaqlı N x M ölçülü matrisdəki hüceyrələr labirintin planını təsvir edir. Hər bir hüceyrə aşağıdakı tam ədədlərlə ifadə olunur:
- 0 – keçilə bilən boş hüceyrə; - 1 – maneə, keçilməz hüceyrə; - 2 – bir qızıl sikkə olan keçilə bilən hüceyrə.
Koordinatları (1,1) olan boş hüceyrə labirintin giriş nöqtəsidir, (N,M) olan boş hüceyrə isə çıxış nöqtəsidir. Cırtdan başlanğıc hüceyrədən hərəkət edərək, məhdud vaxt ərzində, yəni K dəqiqə ərzində son hüceyrəyə çatmalıdır. Cırtdan yalnız qonşu boş hüceyrələrə, onların ortaq tərəfi vasitəsilə hərəkət edə bilər və hər bir hüceyrədən keçmək üçün 1 dəqiqə sərf edir. Labirintdəki qızıl sikkələrin sayı və vaxt məhduddur, məsələn, maksimum 10 ədəd.
Cırtdan, olduğu hüceyrələrdəki bütün sikkələri özü ilə götürə bilər. Yuxarıda göstərilən şərtlər daxilində cırtdan maksimum neçə sikkə toplaya bilər?
Giriş məlumatları: Birinci sətirdə üç ədəd verilir: N, M – matrisin ölçüləri (1<=N,M<=50) və K (1<=K<=100). Növbəti N sətirdə hər birində M ədəd olmaqla labirintin planı təsvir edilir.
Çıxış məlumatları: Bir ədəd – toplanmış maksimum sikkə sayı və ya əgər cırtdan tapşırığı yerinə yetirə bilmirsə -1.