Задача №79. Арбузная грядка
Ограничение по времени: 3 секунды
Ограничение по памяти: 64 мегабайта
На этот раз Вася увлекся выращиванием арбузов. Его огород имеет форму прямоугольника \(N \times M\) метров, разделенного на одинаковые ячейки размером \(1 \times 1\) метр, в каждой из которых растет по арбузу. Как-то раз он решил осмотреть некоторые из них, начав в левом верхнем углу, пройдясь по огороду и вернувшись обратно. Ячейки, оказавшиеся внутри цикла, считаются осмотренными, остальные – не осмотренными. По некоторым банальным соображениям Вася не ходит по грядкам, а только лишь по специальным дорожкам, расположенным на границах ячеек с арбузами. Вдобавок, он хочет, чтобы его путь получился без самопересечений. К счастью, дорожки достаточно широкие для того, чтобы гулять по ним много раз, не считая это за самопересечение (см. рисунки к примерам).
Ваша задача – узнать, за какое минимальное время Васе удастся обойти ровно i арбузов. Можно считать, что он двигается равномерно со скоростью 1 метр в секунду.
Формат входных данных
В первой строке входных данных содержатся два числа \(N, M (1 \le N, M \le 50)\). В следующих N строках идет описание огорода. В (i + 1)-й строке содержатся M символов. Символ "I" на j-й позиции означает, что Вася хочет осмотреть арбуз, расположенный в i-й строке и j-м столбце огорода; символ " ." означает, что ему не важно, что происходит в соответствующей ячейке; символ "X" означает, что он не хочет осматривать это растение. Других символов в строке нет.
Гарантируется, что суммарное количество символов "I" и "X" не превосходит 10, и присутствует хотя бы один символ "I".
Формат выходных данных
Выведите ровно K чисел, разделенных пробелами, где K – количество арбузов, которые Вася хочет осмотреть (количество символов "I" во входном файле). Число номер i должно быть равно минимальному времени, за которое он успеет осмотреть ровно i арбузов, соответствующих символам "I".
Не забудьте учесть, что арбузы, помеченные ".", могут быть осмотрены или нет, но арбузы "X" Вася осматривать не хочет ни в коем случае.
Примеры
|
Входные данные |
Выходные данные |
|
1 1 |
4 |
|
2 2 |
8 |
|
3 3 |
4 6 8 10 12 14 16 18 |
|
3 3 |
8 10 14 |
|
1 10 |
4 6 12 14 20 26 28 |
