| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 2960 | 972 | 741 | 33.348% |
십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.
아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.
...*... ..*.. ...*... .*. ..*.. ...*... * *** ***** ******* .*. ..*.. ...*... ..*.. ...*... ...*...
십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.
크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.
첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.
첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.
5 6 ###### #...#. ###### ##..#. ######
5
아래와 같이 넓이가 1, 5인 십자가를 놓을 수 있다.
###### #...*. #*#*** ##..*. ######
6 6 .#..#. ###### .#..#. ###### .#..#. .#..#.
25
넓이가 5인 십자가 두 개를 놓을 수 있다.
.*..#. ***### .*..*. ###*** .#..*. .#..#.