시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 2 2 33.333%

문제

단위 정사각형으로 나누어져 있는 직사각형 보드가 있다. 각각의 단위 정사각형은 흰색으로 색칠되어져 있다. 이 때, 일부 칸을 검정색으로 칠하려고 한다.

한 번 색칠하는 것은 한 행 또는 한 열에 연속된 흰색 칸을 선택해서 모두 검정색으로 칠하는 것을 의미한다. 최소 몇 번 색칠해야 검정색으로 색칠할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 50) 이 주어진다.

둘째 줄부터 N개의 줄에 색칠해야 하는 칸의 정보가 주어진다. '.'은 흰색으로 남겨야하는 칸, '#'은 검정색으로 색칠해야 하는 칸이다.

출력

최소 몇 번 색칠해야 검정색으로 색칠할 수 있는지 출력한다.

예제 입력

1 5
#####

예제 출력

1

예제 입력 2

5 5
#####
.....
#####
.....
#####

예제 출력 2

3

예제 입력 3

5 5
..#..
..#..
#####
..#..
..#..

예제 출력 3

3

예제 입력 4

5 5
#####
..#..
#####
..#..
#####

예제 출력 4

5

예제 입력 5

5 5
.#.#.
#####
.#.#.
#####
.#.#.

예제 출력 5

8

힌트

출처