시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 256 MB | 135 | 47 | 35 | 32.710% |
백준이는 도장을 좋아한다. 백준이가 사용하는 도장은 직사각형 모양이며, 찍히는 부분은 '#' 기호를 사용한다. 예를 들어, 아래 그림은 백준이의 도장의 예시이다.
..#..#.. .######. ..#..#..
백준이는 빈 종이에 도장을 항상 두 번 찍는다. 먼저, 종이에 도장을 찍은 다음, 도장을 한 번 더 찍는다. 이때, 종이를 돌리면 안되며, 도장을 찍는 위치는 다를 수도 있다. 또, 도장은 항상 종이의 변과 평행하게 찍는다.
'#'는 검정색 잉크가 묻는 부분이고, '.'은 아무 마크도 없는 부분이다. 만약, '#'로 찍힌 종이에 '.'로 표시된 도장의 일부가 찍힌다면, 그대로 '#'를 유지하게 된다. 또, 두 번 찍힌 칸과, 한 번 찍힌 칸은 구분할 수 없다.
도장을 두 번 찍은 종이가 주어졌을 때, 그러한 종이 모양을 만드는 도장 중에서 '#'의 개수가 가장 작은 것을 구하는 프로그램을 작성하시오.
예를 들어, 아래 그림은 위의 도장을 두 번 찍은 모양 중 하나이다.
..#..#.. .######. .######. ..#..#..
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 종이의 길이 L과 너비 W (1 ≤ W, L ≤ 300)가 주어진다. 다음 L개의 줄에는 길이가 W인 문자열이 주어진다. 문자열은 '.'와 '#'로 이루어져 있으며, '#'는 검정 잉크가 묻은 칸, '.'는 빈 칸을 나타낸다.
각각의 테스트 케이스마다 가능한 도장의 '#' 개수가 가장 작은 것을 출력한다.
5 4 8 ..#..#.. .######. .######. ..#..#.. 3 3 ... .#. ... 2 6 .##### #####. 2 5 .#.#. #.#.# 6 6 ###.## #.#### ###### ###### #.#### ######
8 1 5 3 21