E. Design Tutorial: Тоглоомоос сэдэвлэх

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

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

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

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

Шинэ бодлого зохиох нэг арга бол тоглоомоос сэдэвлэх юм. Та тоглоомоо сонгоод, тэр тоглоомын механик хэсэг дээр анхаарлаа хандуулах ёстой, үүний дараа энэ нь сайхан даалгавар байж болох юм.

Туршиж үзье. Японы алдартай Таавар ба Луу гэдэг тоглоом байдаг, бид энэ тоглоомын Таавар хэсэгт анхаарлаа хандуулах болно, энэ нь хавтангуудыг тохируулах таавар юм.

(Зургийг Wikipedia хуудсаас: http://en.wikipedia.org/wiki/Puzzle_&_Dragons)

Бөмбөлөгнүүдээс бүрдсэн $n × m$ самбар байна. Тоглоомын туршид та дараах шилжилтийг хийж болно. Шилжилтийн эхэнд та самбарын нүдэнд хуруугаа хүргэнэ, дараа нь зэргэлдээх нүдрүүдийн (нүднүүдийн зааг дээр байж болохгүй ба 8-н зэргэлдээх нүд байгаа) нэг рүү хуруугаа хөдөлгөж чадна, мөн дараа нь та одоо хуруу байгаа нүднээсээ өөр нэг зэргэлдээх нүдрүү нэг удаа шилжиж чадах ба энэ мэтчилэн явна. Та нэг нүднээс өөр нүдрүү хуруугаа шилжүүлэх бүрд тэдгээр нүднүүд дэх бөмбөлөгнүүд хоорондоо солигдоно. Өөрөөр хэлвэл та ямар ч шилжилт хийхгүйгээр нүдэнд хүрэхэд бөмбөлөг хэзээ ч өөрчлөгдөхгүй байна.

Бөмбөлөгнүүдийг устгаж, таны мангасууд дайснууд руу довтлох маягаар зорилгодоо хүрнэ, гэхдээ бид иймэрхүү нарийн ширийн зүйлсэд анхаарлаа хандуулахгүй. Үүний оронд бид оролтын анхны самбар ба гаралтын зорилтот самбарыг өгөх болно. Таны зорилго бол нэг шилжилтээр зорилгодоо хүрэх арга зам байгаа эсэхийг тодорхойлох юм.

Оролт

Эхний мөр нь хоёр бүхэл тоо агуулна: $n$ ба $m$ $(1 ≤ n, m ≤ 30)$.

Дараагийн $n$ мөр бүр нь $m$ бүхэл тоонууд агуулна -- анхны самбарын тодорхойлолт. $i$-р мөрийн $j$-р бүхэл тоо нь $s_{i, j}$ $(1 ≤ s_{i, j} ≤ 900)$ ба $s_{i, j}$ нь самбарын $i$-р мөр, $j$-р баганан дээр байрлах бөмбөлгийн төрлийг илэрхийлнэ.

Дараагийн $n$ мөрүүд нь ижил форматаар зорилтот самбарыг агуулна. Анхны самбар ба зорилтот самбарууд хоорондоо ялгаатай байхыг анхаарна уу.

Гаралт

Хэрвээ шийдгүй бол гаралт нь -1$ байна.

Шийдтэй бол гаралтын эхний мөр нь $k$ $(1 ≤ k ≤ 10^{6})$ бүхэл тоог агуулна -- хурууны шилжилтын тоо.

Дараашгийн мөрүүд нь $x_{0}$ ба $y_{0}$ $(1 ≤ x_{0} ≤ n; 1 ≤ y_{0} ≤ m$) бүхэл тоонуудыг агуулна -- таны эхлээд хүрсэн нүдний байрлал. Дараагийн $k$ мөр бүрд $x_{i}$, $y_{i}$ $(1 ≤ x_{i} ≤ n; 1 ≤ y_{i} ≤ m)$ бүхэл тоонуудыг хэвлэнэ -- таны шилжилтийн байрлал. Энэ байрлал нь өмнөх байрлалтай зэргэлдээ байх ёстойг анхаарна уу, $max(|x_{i} - x_{i - 1}|, |y_{i} - y_{i - 1}|) = 1$ байна.

Хэрвээ олон шийд байгаа бол та тэдгээрийн аль нэгийг хэвлэж болно. Хэрвээ шийдтэй ба шийд нь $10^{6}$-с илүүгүй үйлдэлтэй бол эдгээр шаардлагуудын дагуу нотлоно.

Орчуулсан: Даариймаа

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

Оролт
2 2
1 3
2 3
1 3
3 2
Гаралт
3
1 1
2 2
2 1
1 1
Оролт
2 2
1 3
2 3
1 2
2 3
Гаралт
-1
Оролт
1 4
1 2 3 4
4 3 2 1
Гаралт
-1
Оролт
4 1
1
2
3
4
3
1
2
4
Гаралт
2
3 1
2 1
1 1
Сэтгэгдлүүдийг ачааллаж байна...