D. Цэгүүдтэй тоглоом

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

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

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

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

Чи дараах тоглоомыг тоглож байна. Хавтгай дээр $n$ цэгүүд байгаа ба эдгээр нь ердийн $n$-олон өнцөгтийн оройнууд юм. Цэгүүд нь $1$-с $n$ хүртэл дугаарлагдсан. Ялгаатай хоёр цэгийн хос бүр диогналиар холбогдсон ба энэ диогналь нь ялгаатай 26 өнгөний аль нэг өнгөтэй байна. Цэгүүдийг Англи жижиг үсгээр тэмдэглэсэн байна. Ялгаатай гурван орой дээр гурван чулуу байрлах ба эдгээр чулуунууд бүгд адилхан байна. Нэг шилжилтээр чулууг ямар нэг диогналийн дагуу өөр нэг чөлөөтэй орой руу шилжүүлж чадна. Энэ диогналийн өнгө нь нөгөө хоёр чулууг холбосон диогналийн өнгөтэй ижилхэн байх ёстой.

Чиний зорилго бол чулуунуудыг $1$, $2$, $3$ оройнуудад байрласан байхаар чулууг нүүлгэх юм. Ийм байрлалд хүрэхийн тулд хамгийн бага тооны шилжилт хийх ёстой. Энэ тоглоомыг оновчтой аргаар тоглох програмыг бич.

Оролт

Эхний мөр нь цэгүүдийн тоо болох $n$ ($3 ≤ n ≤ 70$) бүхэл тоог агуулна. Хоёр дахь мөр нь зайгаар тусгаарлагдсан $1$-с $n$ хүртэлх гурван бүхэл тоог агуулна. Эдгээр тоонууд нь анх чулуу байрласан оройнуудын дугаар юм.

Дараагийн $n$ мөр бүр нь $n$ тэмдэгтүүдийг агуулна. Энэ матриц нь диогналиудын өнгийг илэрхийлнэ. Өнгөнүүдийг Англи жижиг үсгээр төлөөлүүлнэ. $i$-р мөрийн $j$-р тэмдэгт нь $i$ ба $j$ оройнуудыг холбосон диогналийн өнгийг илэрхийлнэ. Тэгэхээр $i$-р мөрийн $j$-р тэмдэгт нь $j$-р мөрийн $i$-р тэмдэгттэй ижил байна. Гол диогналийг '$*$' тэмдгээр дүүргэсэн, учир нь энд диогналь байхгүй, цэгийг өөртэй нь холбоно.

Гаралт

Хэрвээ чулуунуудыг $1$, $2$, $3$ оройнуудад тавих боломжгүй бол нэг мөрөнд $-1$ гэж хэвлэнэ. Эсрэг тохиолдолд эхний мөрөнд шаардсан хамгийн бага шилжилтийн тоог хэвлэх ба дараагийн мөрүүдэд шилжилт бүрийн тодорхойлолтыг нэг мөрөнд хэвлэнэ. Шилжилтийн тодорхойлолт нь хоёр бүхэл тоо байна. Энэ нь чулууг авсан цэг болон шилжүүлж тавьсан цэг юм. Хэрвээ хэд хэдэн тохиромжтой шийдэл байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

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

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

Оролт
4
2 3 4
*aba
a*ab
ba*b
abb*
Гаралт
1
4 1
Оролт
4
2 3 4
*abc
a*ab
ba*b
cbb*
Гаралт
-1

Тэмдэглэл

Эхний жишээнд бид $4$ цэг дээрх чулууг шилжүүлж $1$ цэг дээр тавина. Учир нь энэ цэгүүд '$a$' өнгөтэй диогналиар холбогдсон ба бусад чулуунууд байрласан $2$, $3$ цэгүүд ижил өнгөтэй диогналиар холбогдсон. Үүний дараа чулуунууд $1$, $2$, $3$ цэгүүд дээр байна.

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