Masala H

Xotira 32 MB Vaqt 1000 ms

Yo'lni toping! [HARD]

Muhammadali uyidan bog'chaga o'zini ukasini Abduazimni olishi kerak, lekin u tez borishi kerak. Abduazim aytishi bo'yicha u kuchiklardan qorqadi shuning uchun u kuchuklar yo'q yo'llardan borishi kerak. Muhammadali $(0,0)$ kordinatada turibdi va $1$ raqami bu kuchuk yo'q yo'lalr, $0$ esa kuchuk bor yo'l. Va yo'llar bir biri bilan ulanishi zarur, agar ulanmagan bo'lsa $-1$ chop eting!

Kiruvchi ma'lumotlar:

Sizga $N$ va $NxN (1≤N≤20)$ matritsa beriladi va siz kuchuk lar yo'q yolni chiqarishiz kerak.

Chiquvchi ma'lumotlar:

Muhammadali yurishi kerak bo'lgan yo'llar. (eng qisqa yo'l)

Misollar

#	input.txt	output.txt
1	4 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0	1 1 1 1
2	3 1 0 1 0 1 0 0 0 1	1 1 1