B. Нууцат өрөө

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

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

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

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

"Нууцат өрөө дахин онгойжээ" -- энэ мэдээ Хогварт-аар тарсан бөгөөд хэсэг сурагчид Басилиск-ийг харснаас болж аль хэдийн хөшсөн байв. Дамбалдоор аль хэдийн ажлаасаа халагдсан ба одоо Харри нууцат өрөө уруу орохыг оролдож байв. Харин энэ нь харанхуйн эзэн Волдиморт-ын хувьд тийм ч сайн мэдээ биш байлаа. Тэрээр хэнийг ч өрөөнд орж ирэхийг хүсэхгүй байв. Учир нь одоо тэрээр Жинни-ын амьдралыг өөртөө сорон завгүй байгаа юм.

Нууцат өрөө гэдэг нь $n × m$ хэмжээ бүхий тэгш өнцөгт хүснэгт бөгөөд зарим нүднүүд дээр нь баганууд байрлаж байв. Гэрлийн тусгал (өөрөөр хэлбэл Басилиск-ийн ширтсэн харц) эдгээр багануудыг нэвтрэн чиглэлээ өөрчлөхгүйгээр явах юм. Гэвч нэгэн ид шидийн тусламжтайгаар бид ямар нэгэн баганыг шидэт багана болгож болох бөгөөд ингэснээр уг багана уруу гэрлийн тусгал тусах үед гэрлийн тусгал нь бүх 4-н чиглэл уруу ойн тусах ажээ. Уг үзэгдлийг доорх зурагт дүрслэв.

Зүүн талын гэрлийн тусгал нь энгийн баганаар нэвтрэн өнгөрч байгаа бол баруун талын тусгал нь шидэт баганаар нэвтрэн 4-н чиглэл уруу тусаж байна.

Басилиск хүснэгтийн баруун доод нүдний баруун талд байрлаж байгаа бөгөөд зүүн тийш харж байна (өөрөөр хэлбэл зүүн доод нүд уруу чиглэн харж байх юм). Домогт өгүүлснээр Басилиск-ийн харц уруу шууд байдлаар харсан хэн ч бай тэр даруй үхдэг билээ. Хэрэв хэн нэгэн Басилиск-ийн харцыг баганаар дамжуулан харвал тухайн хүн хөшдөг байв. Бидний мэдэж байгаачлан өрөөний хаалга хүснэгтийн зүүн дээд булангийн зүүн талд байрлах бөгөөд уг хаалгаар орж ирэх хүн болгон нь уг хаалганы байрлалаас өөрийн хөдлөх чиглэлийн дагуу харах юм. Өөрөөр хэлбэл баруун дээд нүдний чиглэлд харна гэсэн үг юм.

Уг зурагт эхний жишээг дүрслэв.

Өрөөний хэмжээ болон энгийн багануудын байрлал өгөгдсөн бөгөөд харанхуйн эзэн Волдиморт таныг өрөөнд орж ирэхийг хүссэн хэн боловч хөшиж байхаар эсвэл өрөөнд аюулгүй байх боломжгүй байхаар хамгийн багадаа хэчнээн тооны баганыг шидэт багана болгох ёстойг хэлж өгөхийг хүсжээ.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n, m ≤ 1000$) өгөгдөнө. Дараагийн $n$ ширхэг мөрийн мөр болгонд $m$ ширхэг тэмдэгт өгөгдөнө. Тэмдэгт болгон нь "." эсвэл "#" байх бөгөөд эдгээр нь өрөөг дүрслэх хүснэгтийн нэг нүдийг илэрхийлэх юм. Хэрэв харгалзах нүд нь хоосон байвал "." гэсэн тэмдэгт өгөгдөх ба энгийн багана агуулж байвал "#" гэсэн тэмдэгт өгөгдөнө.

Гаралт

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

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

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

Оролт
3 3
.#.
...
.#.
Гаралт
2
Оролт
4 3
##.
...
.#.
.#.
Гаралт
2

Тэмдэглэл

Дээр өгөгдсөн зурагт эхний жишээг дүрсэлж байна. Эхний жишээнд бид өгөгдсөн 2 баганыг 2-ууланг нь шидэт багана болгох юм. Зурган дээрх луу нь Басилиск-ийг дүрслэх бөгөөд 2 нүдний дуран нь нууцат өрөөнд орж ирэх хүнийг дүрсэлнэ. Хар од нь уг хүний хөших газрыг илэрхийлнэ. Харин шар шулуунууд нь багануудаар дамжин хөдлөх Басилиск-ийн харцыг илэрхийлнэ.

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