A. Цэвэрлэгээ

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

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

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

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

Та бол одоо чөтгөрийн гүүрэн дотор аялаж буй адал явдал хайгч. Та хоёр ч сул дорой зомбиг устгасаныхаа дараа $n × n$ хүснэгт бүхий хавтангуудаас бүрдсэн дөрвөлжин өрөөнд ирсэн. Мөрүүд дээрээсээ доош $1$-c $n$ хүртэл дугаарлагдсан ба баганууд зүүнээсээ баруун тийш $1$-c $n$ хүртэл дугаарлагдсан. Өрөөний нөгөө талд чөтгөрийн шидийн хүчээр цоожлогдсон хаалга байна. Хаалган дээр дараах бичээс байна.

Бүх чөтгөрийг цэвэрлэх нь хаалгыг сэрээнэ!

Ахмад аялагчийн хувьд та энэ зүйл юу илэрхийлж байгааг шууд л мэдсэн. Та анхандаа нүд бүрт чөтгөр байгааг анзаарсан. Та эдгээр бүх нүдийг цэвэрлэх ёстой.

Тухайн хавтанг цэвэрлэх таны мэдэх ганцхан арга нь "Purification" тарнийг цутгах юм. Та энэ тарнийг нэг хавтан дээр цутгах ба ингээд уг нүдтэй нэг мөр болон баганад байрласан бүх нүднүүд цэвэрлэгдэнэ (сонгогдсон хавтанг оруулаад). Нэг нүдийг нэгээс олон удаа цэвэрлэх боломжтой.

Та "Purification" тарнийг хамгийн бага тооны удаа цутгаад бүх $n × n$ нүдийг цэвэрлэхийг хүсч байна. Энэ маш амархан сонсогдож байгаа боловч та зарим хавтанд бусад хавтнаас илүү чөтгөртэй байгааг анзаарсан. Та эдгээр илүү чөтгөртэй нүдэнд цэвэрлэгдсэнийх нь дараа ч гэсэн "Purification" тарнийг цутгах боломжгүй. Тэд нар ч гэсэн байрлаж буй мөр эсвэл багана нь "Purification" тарни бичигдэхээр сонгогдох юм бол цэвэрлэгдэнэ.

Хамгийн цөөн тооны тарни цутгах замаар бүх нүдийг цэвэрлэх аргыг олно уу. Хэрвээ ийм арга олдохгүй бол -1-ийг хэвлэ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 100$) байна. Тэгээд тус бүртээ $n$ тэмдэгттэй $n$ мөр байна. $i$-р мөрийн $j$-р тэмдэгт нь $i$-р мөр $j$-р баганад байгаа нүдийг илэрхийлнэ. Хэрвээ уг нүд илүү чөтгөртэй байвал уг тэмдэгт нь '$E$' байх бол бусад тохиолдолд '$.$' байна.

Гаралт

Бүх нүдийг цэвэрлэх ямар ч арга байхгүй бол -1-ийг хэвлэ. Бусад тохиолдолд буюу таны шийдэл $x$ "Purification" тарнийг (энд $x$ нь тарнийн боломжит хамгийн бага тоо) цутгах бол $x$ мөр хэвлэнэ. Мөр бүрт таны "Purification" тарнийг цутгах нүдний мөр болон баганын дугаарыг илэрхийлэх хоёр бүхэл тоог агуулна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3
.E.
E.E
.E.
Гаралт
1 1
2 2
3 3
Оролт
3
EEE
E..
E.E
Гаралт
-1
Оролт
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE
Гаралт
3 3
1 3
2 2
4 4
5 3

Тэмдэглэл

Эхний жишээг дараах байдлаар дүрсэлж болно. Ягаан хавтангууд нь хараахан цэвэрлээгүй байгаа чөтгөртэй хавтангууд юм. "Purification" тарнийг цутгасан хавтанг улаан өнгөөр дүрслэсэн байна. Харин шар өнгөөр одоогийн "Purification" тарнийн нөлөөгөөр цэвэрлэгдэж буй хавтангуудыг харуулсан байна. Өмнө нь цэвэрлэгдсэн хавтангуудыг ногоон өнгөөр дүрслэн харуулав.

Хоёр дахь жишээн дээр $1$-р мөр $1$-р баганад байгаа нүдийг цэвэрлэх боломжгүй.

Гуравдугаар жишээний хувьд:

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