13444번 - 보드 색칠하기

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

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

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

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

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