C. 3 хот

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

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

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

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

Дэлхийн эдийн засгийн хямралаас үүдэн Берман, Беранс, Берталийн удирдлагууд тус тусын хилээ нээж оршин суугчиддаа 3 хотоор чөлөөтэй зорчих боломж олгожээ. Үүнтэй зэрэгцэн аль нэг улсын дурын цэгээс өөр нэг улсын дурын цэгт очих боломжтой зам барьж эхэлсэн байна.

Тус ажил их мөнгө шаардах нь мэдээж. Ингээд хотын удирдлагууд таниас замын өртгийг багасгах талаар зөвлөгөө авахаар шийджээ. Та үүний тулд $n$ х $m$ хэмжээтэй хүснэгтийг ашиглах ёстой. Хүснэгтийн дурын нүд 3 хотын аль нэгийг эсвэл зам барьж болох, болохгүй газрыг илтгэнэ. Хэрэв хүснэгтийн нэг нүд 3 хотын аль нэгийг, эсвэл зам тавьж болох хэсгийг илтгэж байгаа бол тус нүдийг "нээлттэй зам" гэж үзнэ. Хэрвээ хөдөлгөөнд харгалзаж буй нүд нь оршин байх ба нээлттэй байвал та тус "нээлттэй" нүднээс дээш доош, баруун зүүн тийш аль ч чиглэлд явж болно.

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

Хотын аль ч хэсэгт очих боломж ямар ч тохиолдолд олддог нүд 3 хотод дор хаяж нэг нэг байдаг гэж үз.

Оролт

Эхний мөрөнд $n$ х $m$ ($1 ≤ n, m ≤ 1000$) газрын зурагны хэмжээг оруулна. ($n$ - мөр, $m$ - багана)

Дараагийн $n$ мөр бүр $m$ тэмдэгт агуулна. Тус $m$ тэмдэгт газрын зурагны мөрийг илтгэнэ. 1-ээс 3 дахь тоо хоорондоо таарч байгаа хотын тоог, $.$ - ээр зам барих боломжтой нүдийг, $#$ - ээр боломжгүй нүдийг тэмдэглэнэ.

Гаралт

Хотын аль ч хэсэгт очих боломжтой нүдний хамгийн бага утгыг хэвлэнэ. Хэрэв боломжгүй гэвэл $-1$ ийг хэвлэнэ.

Орчуулсан: ERDENI

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

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