Codeforces Beta Round 14 (Див. 2) |
---|
Закончено |
Мальчик Ваня очень любит рисовать. Недавно он купил прямоугольный лист клетчатой бумаги из n строк и m столбцов. Ваня заштриховал на нём некоторые клетки. Увидев свой шедевр, он решил поделиться им со своим старшим братом, который живёт во Флатландии. Теперь Ване надо послать картину по почте, но в связи с мировым финансовым кризисом и высокими ценами на нефть, он хочет сделать это, потратив как можно меньше денег. За каждую отосланную клеточку бумаги (независимо от того заштрихована клетка или нет) Ваня должен заплатить 3.14 бурлей. Помогите Ване вырезать из шедевра прямоугольник наименьшей стоимости, содержащий все зашрихованные клетки. Стороны прямоугольника должны быть параллельны сторонам листа бумаги.
В первой строке входных данных находятся числа n и m (1 ≤ n, m ≤ 50), n — количество строк, а m — количество столбцов на листе бумаги Вани. В следующих n строках содержится по m символов. Символ «.» обозначает незаштрихованную клетку листа бумаги, а «*» — заштрихованную. Гарантируется, что Ваня заштриховал хотя бы одну клетку.
Выведите искомый наименьший по стоимости прямоугольник. Смотрите примеры выходных данных для уточнения формата вывода.
6 7
.......
..***..
..*....
..***..
..*....
..***..
***
*..
***
*..
***
3 3
***
*.*
***
***
*.*
***
Название |
---|