Hərşeyə Qadirlik Plitələri#5061
Lord Benedict Qara Lordun qalasından cəsarətli qaçışı zamanı özünü Qara Qalanın xəzinəsində tapır. Bu xəzinə otağı N \times N ölçülü kvadrat otaqdan ibarətdir. Benedict sol yuxarı hüceyrədə başlayır, çıxış isə sağ aşağı hüceyrədə yerləşir. Bu hüceyrələrin bəzilərində Qüdrət Döşəməsi yerləşir. Benedictin məqsədi otaqdan çıxmaqdır və o, bu döşəmələrdən mümkün qədər çoxunu keçməyə çalışır. Baxmayaraq ki, o, bütün döşəmələri keçə bilərdi, "İldırımsürətli Çəkmələri" ona yalnız sağa və ya aşağıya hərəkət etməyə imkan verir, bu isə onun seçimlərini məhdudlaşdırır və düzgün yol seçimi tələb edir.
Birinci sətirdə tam ədədi verilir (1 \leq N \leq 500). Sonrakı sətrin hər birində xəzinə otağının təsviri olan tam ədəd verilir; təsvir sol yuxarı hüceyrədən başlayıb sağ aşağı hüceyrədə bitir. ədəd boş hüceyrəni, isə Qüdrət Döşəməsi olan hüceyrəni bildirir. Qeyd edək ki, sol yuxarı və sağ aşağı hüceyrələrdə döşəmə olmur.
Benedictin çıxışa gedən yolunda keçə biləcəyi maksimum Qüdrət Döşəməsi sayını çap edin.
Nümunə 1