십자가 2개 놓기

면접 대비

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

요약
'.'과 '#'으로 이루어진 작은 격자에 서로 겹치지 않는 십자가 두 개를 놓고 두 넓이의 곱이 최대가 되도록 한다.
난이도

보통10점 중 5점

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

문제

십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.

아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.

                  ...*...
          ..*..   ...*...
    .*.   ..*..   ...*...
*   ***   *****   *******
    .*.   ..*..   ...*...
          ..*..   ...*...
                  ...*...

십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.

크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.

입력

첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.

예제2

  1. 예제 1

    입력
    5 6
######
#...#.
######
##..#.
######
    예상 출력
    5

  2. 예제 2

    입력
    6 6
.#..#.
######
.#..#.
######
.#..#.
.#..#.
    예상 출력
    25