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

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

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

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

Оролт

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

Гаралт

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

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

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
3
1 2 3
4 5 6
7 8 9
Гаралт
0
DDRR
Сэтгэгдлүүдийг ачааллаж байна...