Олимпиадный тренинг

Задача 34780. Lake house


Задача

Темы:
There is a lake next to which they want to build a house. The architectural project (the shape of the house) has already been approved, you can only choose the location of the house so that it is next to the lake. It is advisable to choose the location of the house near the lake so that as many residents of the house as possible have windows overlooking the lake, that is, so that the length of the common border between the house and the lake is maximum.

The plan of the house and the lake is given as an image on checkered paper, in which the cells belonging to the house and the lake are marked. The first line of the input contains the number N – the number of rows in the plan of the house and the lake. The second line of the input contains the number M – number of columns in house and lake plan.

The next N lines contain M characters each – house plan. The character "." in these lines denotes an empty cell, the symbol "H" denotes» denotes a house cell. The house plan is a connected area and does not contain "holes"; inside. There is at least one cell in the plan that belongs to the house. The next N lines of M characters each contain the plan of the lake, in these lines the character "." denotes an empty cell, the symbol "W" denotes a cell occupied by a lake. Plan» denotes a cell occupied by a lake. The plan of the lake is a connected area and does not contain "holes"; inside. There is at least one cell in the plan that belongs to the lake.

The program should output a single number – the maximum value of the length of the common border of the house and the lake, measured in the sides of the cell. When the house is located next to the lake, it can be moved, but you can not make turns and reflections. There is unlimited free space around the lake, the house can be located on either side of the lake.
The numbers N and M are integers, positive, do not exceed 15.
 
Input Output Note
5
6
......
.HHHH.
.HHHH.
.HHHH.
......
..WWW.
..WWW.
..WWW.
..WWW.
..WWW.
3       . . . . W W W
H H H H W W W
H H H H W W W
H H H H W W W
      . . . . W W W
5
7
...HHH.
.H...H.
.HHHH.
.H.H...
.HHH...
......
..WWWW
WWW...W
W.W...W
..W....
11