A. Зураг хайчлах

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

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

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

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

Чамд квадратуудад хуваагдсан $n × m$ хэмжээтэй цаас өгөгднө. Квадратуудын зарим нь будагдсан. Бүх будагдсан квадратуудын олонлогийг $A$ гэе. $A$ олонлог нь холбоост байна. Чиний даалгавар бол хамгийн багадаа хэдэн квадратыг хайчлан $A$ олонлогийг холбоост биш болгож чадахыг олох юм.

Будагдсан квадратуудын олонлогийн дурын хоёр $a$ ба $b$ гэсэн квадратуудын хувьд $a$-аас $b$ хүртэл очдог байхаар(хөрш квадратаар дамжих) тухайн олонлогоос дараалал олддог байвал тэр олонлогийг холбоост гэнэ. Тодорхойлолт ёсоор хоосон олонлог эсвэл нэг элемэнттэй олонлог нь холбоост юм.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n$ ба $m$ ($1 ≤ n, m ≤ 50$) бүхэл тоонууд байна, энэ нь цаасний хэмжээ.

Дараагийн $n$ мөр бүрт $m$ ширхэг тэмдэгт байрна -- Цаасний будагдсан хэсгийг илрхийлэх нь: $i$ дүгээр мөрний $j$ дүгээр тэмдэгт нЬ будагдсан бол "#" байна үгүй бол "." байна. Мөн $A$ олонлог нь өгөгдөлд хоосон биш холбоост байх болно.

Гаралт

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

Орчуулсан: Бат-Од

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

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

Тэмдэглэл

Эхний жишээнд дурын 2 хөрш биш квадратуудыг арилгахад л болно.

Дараагийн жишээндэх зургийг дүрлэсэн байна. Зүүн хэсэгт анхны цаас байна. Баруун хэсэгт хайчилсан цаас байна. Хайчилсан квадратууд нь кросстой байна.

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