Задача №114190. Дом у озера
Есть озеро, рядом с которым хотят построить дом. Архитектурный проект (форма дома) уже утверждён, можно только выбрать расположение дома так, чтобы он оказался рядом с озером. Желательно выбрать расположение дома рядом с озером так, чтобы у как можно большего числа жителей дома окна выходили на озеро, то есть чтобы длина общей границы дома и озера была максимальной.
План дома и озера задан в виде изображения на клетчатой бумаге, в котором отмечены клетки, принадлежащие дому и озеру. Первая строка входных данных содержит число \(N\) –количество строк в плане дома и озера. Вторая строка входных данных содержит число \(M\) –количество столбцов в плане дома и озера.
Следующие \(N\) строк содержат по \(M\) символов – план дома. Символ «.» в этих строках обозначает пустую клетку, символ «H» обозначает» обозначает клетку дома. План дома является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая дому.
Следующие \(N\) строк по \(M\) символов в каждой содержат план озера, в этих строках символ «.» обозначает пустую клетку, символ «W» обозначает клетку, занятую озером. План озера является связной областью и не содержит «дырок» внутри. В плане есть хотя бы одна клетка, принадлежащая озеру.
Числа \(N\) и \(M\) являются целыми, положительными, не превосходят 15.
Программа должна вывести одно число – максимальное значение длины общей границы дома и озера, измеряемую в сторонах клетки. При расположении дома рядом с озером его можно передвигать, но нельзя делать повороты и отражения. Вокруг озера есть неограниченное свободное пространство, дом может располагаться с любой стороны от озера.
Пример наилучшего размещения для первого теста:
Пример наилучшего размещения для второго теста:
Решение, правильно работающее только для случаев, когда дом и озеро являются прямоугольниками, будет оцениваться в 40 баллов.
Решение будет оцениваться, только если оно проходит первый тест из условия задачи(прохождение второго теста обязательным не является).
5 6 ...... .HHHH. .HHHH. .HHHH. ...... ..WWW. ..WWW. ..WWW. ..WWW. ..WWW.
3
5 7 ...HHH. .H...H. .H.HHH. .H.H... .HHH... ....... ..WWWWW WWW...W W.W...W ..W....
11