만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

햄스터 케이지

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

요약
두 큐브 도형을 탁자 위에 배치하여 햄스터가 빠져나갈 수 없는 영역의 최대 넓이를 구합니다.
난이도

보통10점 중 7점

유형
완전 탐색, 시뮬레이션, BFS
정답자
아직 제출이 없습니다

문제

안드류샤는 생일 선물로 햄스터를 받았다. 케이지를 살 때까지 작년에 받은 큐브 세트로 주변 재료를 이용해 케이지를 만들려고 한다. 그런데 누나가 큐브를 전부 슈퍼글루로 붙여 버려서 하나씩 떼어 낼 수 없다.

큐브는 두 개의 도형을 이룬다. 각 도형에서 임의의 두 큐브는 점을 공유하지 않거나, 면을 공유하거나, 모서리를 공유한다. 모서리를 공유하는 경우에는 두 큐브 모두와 면을 공유하는 큐브가 하나 있다. 각 도형은 모든 큐브가 한 면으로 탁자에 닿도록 탁자 위에 놓을 수 있다.

이제 안드류샤는 두 도형을 탁자 위에 놓아 햄스터 케이지를 만들려고 한다. 모든 큐브는 바닥면 하나로 탁자에 닿아야 한다. 바닥면의 변은 탁자의 변과 평행해야 한다. 서로 다른 도형에 속한 임의의 두 큐브는 닿지 않거나, 면을 공유하거나, 모서리를 공유해야 한다. 도형은 회전하거나 뒤집을 수 있다.

도형을 놓은 뒤 안드류샤는 햄스터를 탁자 위에 풀어 준다. 햄스터가 떨어지지 않으려면 풀어 준 지점에서 탁자 가장자리까지 가는 길이 없어야 한다. 햄스터는 큐브를 넘을 수 없고, 모서리를 공유하는 두 큐브 사이를 빠져나갈 수도 없다. 탁자는 각 도형보다 훨씬 크다.

안드류샤는 햄스터가 돌아다닐 수 있는 면적을 최대한 넓히고 싶어 한다. 햄스터가 도달할 수 있는 영역의 최대 넓이를 구하라. 큐브 한 면의 넓이는 1이다. 케이지를 만들 수 없으면 0이다.

위 그림의 두 도형은 다음 그림처럼 놓을 수 있다. 화살표로 표시한 지점에 햄스터를 풀어 주면 도달할 수 있는 영역의 넓이는 4이다.

입력

첫 줄에 두 정수 h1h_1과 w1w_1 (1≤h1,w1≤101 \le h_1, w_1 \le 10)이 주어진다. 이어서 h1h_1개의 줄에 각각 w1w_1개의 문자가 주어지며, 첫 번째 도형을 위에서 본 모습이다. 각 문자는 큐브를 뜻하는 * 또는 빈 칸을 뜻하는 .이다.

다음 줄에 두 정수 h2h_2와 w2w_2 (1≤h2,w2≤101 \le h_2, w_2 \le 10)가 주어진다. 이어서 h2h_2개의 줄에 같은 형식으로 두 번째 도형이 주어진다.

각 도형은 연결되어 있고 큐브를 하나 이상 포함한다.

출력

햄스터가 도달할 수 있는 최대 넓이를 한 정수로 출력한다. 케이지를 만들 수 없으면 0을 출력한다.

예제1

  1. 예제 1

    입력
    8 8
    ........
    .***....
    ..**....
    .*****..
    ...*.*..
    ...***..
    ****....
    ........
    8 8
    ........
    ........
    ........
    ........
    *******.
    ........
    ........
    ........
    
    예상 출력
    4