002-B.md

Хамгийн бага тойрогтой зам

Танд сөрөг биш бүхэл тооноос тогтох $n × n$ хүснэгт өгөгдсөн. Та уг хүснэгтээс дараах нөхцлийг хангах замыг олоорой

• Хүснэгтийн зүүн дээд булангаас эхлэх
• Дараагийн нүд нь одоо байгаа нүдний баруун эсвэл доод талынх байх
• Зам баруун доод буланд дуусах

Мөн бид сонгосон замаар явж дууссаны дараа дайрсан нүднүүд дахь тооны үржвэр "хамгийн бага тойрогтой" байх ёстой. Энэ нь уг үржвэр хамгийн цөөн $0$ -р төгсөх ёстой гэсэн үг юм.

Оролт

Эхний мөр хүснэгтний хэмжээ болох $n$ бүхэл тоо байна ($2 ≤ n ≤ 1000$). Дараагийн $n$ мөрөнд хүснэгтийн элементүүд өгөгдөнө. (утгууд нь $10^9$ -с хэтрэхгүй эерэг бүхэл тоонууд)

Гаралт

Эхний мөрөнд хамгийн цөөн байх үржвэрийн төгсгөл дахь $0$-н тоог гарга.

Дараагийн мөрөнд явах замыг хэвлэнэ.

-- zoloogg