D. Инна ба чихэрлэг матриц

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

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

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

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

Инна чихэрлэг зүйлд үнэхээр дуртай.Тиймээс тэрээр чихэрлэг матриц гэх тоглоомыг тоглохоор шийджээ.

Инна-д $n × m$ матриц болон $k$ ширхэг чихэр харагдаж байгаа.Бид матрицийн мөрийг $1$-ээс $n$ хүртэл баганыг $1$-ээс $m$ хүртэл дугаарлах ба бид $i$-дахь мөр болон $j$-дэх баганын нүдийг $(i, j)$ гэж тэмдэглэнэ.Хэрэв $|i - p| + |j - q| = 1$ байвал матрицийн $(i, j)$ болон $(p, q)$ 2 нүдийг зэргэлдээ гэж үзэх ба зам гэдэг нь дарааллын хөрш 2 нүд бүр нь зэргэлдээ байх матрицийн дарааллыг хэлнэ.Мөн бид уг дарааллын нүдний тоог замын урт гэж нэрлэнэ.

Матрицийн нүд бүр нь хамгийн ихдээ нэг чихэртэй байна.Анхандаа бүх нүд нь хоосон байх бөгөөд Инна матрицад $k$ ширхэг чихрүүдийг нэг нэгээр нь байрлуулахыг оролдох юм.Чихэр бүрийн хувьд Инна чихрээ тавих $(i, j)$ нүд сонгох ба мөн $(1, 1)$ нүднээс эхлээд ямар ч чихэр агуулаагүй $(i, j)$ нүд дээр дуусах зам сонгох юм.Үүний дараа Инна чихрээ $(1, 1)$ нүднээс $(i, j)$ нүд хүртэлх замын дагуу хөдөлгөх ба чихэр энэ зам дээрээ үүрд үлдэнэ.Хэрэв ямар нэг мөчид Инна ямар нэг зам сонгож чадахгүй бол тэрээр хожигдоно.Хэрэв Инна дүрслэгдсэн аргаар матрицад бүх чихрийг байрлуулж чадвал түүний шийтгэл нь түүний хэрэглэсэн замуудын уртын нийлбэртэй тэнцүү байна.

Инна-д тоглоомын шийтгэлийг хамгийн бага болгож тусална уу.

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $k$ $(1 ≤ n, m ≤ 50, 1 ≤ k ≤ n*m)$ өгөгдөнө.

Гаралт

Эхний мөрөнд Инна-ийн тоглоомын хамгийн бага шийтгэлийг илэрхийлэх бүхэл тоог хэвлэнэ.

Дараагийн $k$ мөрөнд чихэр бүрийн хувьд замын тайлбарыг хэвлэнэ.$i$-дахь ээлжид тавигдсан чихрийн замын тайлбар доорх $i$-дахь мөрөнд байна.Замын тайлбар нь нүднүүдийг дараалал байна.Нүд бүр нь $(i, j)$ хэлбэрээр бичигдэх ба энд $i$-аар мөрийн дугаарыг $j$-ээр баганын дугаарыг тэмдэглэв.Та нэг мөрөнд илүү цагаан хоосон зайг хэвлэж болно.Хэрэв олон тооны хариулт байвал алийг нь ч хэвлэсэн болно.

Гаралтын хэлбэрийг сайтар дагна уу! Хэрэв таны программ эхний шалгагч тестийг давбал таны хэлбэр зөв байна гэсэн үг.

Орчуулсан: Баатархүү

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

Оролт
4 4 4
Гаралт
8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)

Тэмдэглэл

Жишээнд тайлбар хийе. Анхандаа матриц нь хоосон байна.Дараа нь Инна эхний замаа дагах ба замын шийтгэл нь нүдний тоотой тэнцүү байна -- 3.Одоо (2, 2) нүд чихэртэй учраас ямар ч зам уг нүдээр өнгөрч болохгүйг анхаарна уу.Дараагийн 2 чихэр нь (1, 2) болон (2, 1) гэсэн цэг дээр байрлана.Инна хялбархан сүүлийн чихрээ зөвхөн (1, 1) нүдийг агуулах замын тус нүд дээр байрлуулна.Ингэснээр нийт шийтгэл нь: 3 + 2 + 2 + 1 = 8 болох юм.

Инна (1, 1) нүдийг байрлуулахад ашиглаж чадахгүй байсныг анхаарна уу, жишээ нь энэ тохиолдолд 3-дахь чихрийн хувьд тэрээр 4-дэх чихрийн замыг ашиглаж болохгүй байсан.

Сэтгэгдлүүдийг ачааллаж байна...