Головоломка

시간 제한1초메모리 제한1024 MB

요약

연결된 폴리오미노 조각을 연결된 장애물 위에 수평으로 놓고 곧장 떨어뜨려 멈출 때, 장애물 칸 바로 오른쪽에 조각 칸이 오는 수평 접촉 쌍의 수를 최대로 만드는 문제입니다. n_f, m_f, n_o, m_o는 각각 300 이하입니다. 조각과 장애물은 모두 비어 있지 않고 변으로 연결되어 있습니다. 점수는 0부터 시작하며, 조각이 장애물에 닿지 않고 통과하면 점수는 0입니다. 모든 수평 위치를 시도해 최댓값을 구해야 합니다.

난이도: 보통10점 중 7점
유형: 기하, 완전 탐색, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

Дима играет в логическую компьютерную игру. Очередной уровень устроен следующим образом: у Димы есть клетчатая фигура, составленная из единичных квадратов. Ее необходимо правильным образом уронить на препятствие, также составленное из единичных квадратов. Фигура и препятствие являются связными: от любого квадрата фигуры можно добраться до любого другого, переходя между квадратами по стороне, аналогичное свойство выполнено для препятствия.

Исходно фигура находится сверху над препятствием так, что любой квадрат фигуры выше любого квадрата препятствия. Дима может произвольным образом переместить фигуру по горизонтали, а затем нажать на специальную кнопку, и фигура опустится вниз до упора. После этого за каждую пару соседних по горизонтали единичных квадратов, таких что левый квадрат принадлежит препятствию, а правый --- фигуре, Дима получает одно очко. Если Дима расположит фигуру так, что при падении вниз она не упрётся в препятствие, то Дима не получит очков.

Помогите Диме решить головоломку оптимальным образом.

Например, если у Димы есть фигура и препятствие, показанные на рисунке ниже, выгоднее всего уронить фигуру следующим образом:

В этом случае количество очков, набранных Димой, будет равно 4.

입력

В первой строке ввода содержатся два числа $n\_f$ и $m\_f$ --- размеры фигуры ( $1 \le n\_f, m\_f \le 300$ ). В каждой из следующих $n\_f$ строк содержатся по $m\_f$ символов --- описание фигуры, <<*>> означает квадрат, принадлежащий фигуре, <<.>> --- пустой квадрат.

В следующей строке содержатся два числа $n\_o$ и $m\_o$ --- размеры препятствия ( $1 \le n\_o, m\_o \le 300$ ). В каждой из следующих $n\_o$ строк содержатся по $m\_o$ символов --- описание препятствия, <<#>> означает квадрат, принадлежащий препятствию, <<.>> --- пустой квадрат.

Гарантируется, что фигура и препятствие представляют собой непустые связные множества единичных квадратов.

출력

Выведите максимальное количество очков, которое Дима может получить.

힌트

В тестовом примере оптимальный способ уронить фигуру показан на рисунке в условии.

예제1

예제 1

입력

5 6
******
*.*.*.
*.*.*.
*.....
*.....
3 8
#.#.#.#.
#.#.#.#.
#######.

예상 출력