시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2427 | 771 | 584 | 33.238% |
십자가는 가운데에 '*
'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*
'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*
'의 개수이다. 십자가의 크기는 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인 십자가 두 개를 놓을 수 있다.
.*..#. ***### .*..*. ###*** .#..*. .#..#.