문제
비어있는 높이 N, 너비 M의 격자 판이 있다(비어있는 공간은 '.'로 표기한다.)
이러한 격자판에 ‘*****’가 새겨진 막대를 이용하여 입력받은 패턴을 재현할 수 있는지 없는지 판단하고,
가능 할 경우 사용되는 막대의 최소 개수를 알아내는 프로그램을 제작하고자 한다.
막대에 새겨진 한 글자와 격자 판의 한 칸의 크기는 일치한다.
막대는 격자 판 내에 놓여야 하며, 수는 제한이 없다.
막대끼리 겹칠 수 있으며, 수직으로, 수평으로만 놓을 수 있다.
아래와 같은 패턴이 입력되었을 경우 2번째 열에 수직으로 막대를 하나,
2번째 행에 두 번째 열에 수평으로 막대를 하나,
마지막으로 4번째 행 첫 번째 열에 수평으로 막대를 하나 놓게 되면 3개의 막대로 패턴을 완성시킬 수 있다.
.*....
.*****
.*....
*****.
.*....
입력
첫줄에는 격자판의 높이 N 너비 M이 입력된다(1≤N≤5, 1≤M≤10).
그 다음 줄부터 N x M 크기의 패턴이 입력된다.
비어있는 칸은 ‘.’로 채워져야 하는 칸은 ‘*’로 표시한다.
출력
입력된 패턴을 만들 수 없을 경우 -1을
0개 이상의 "*****"가 새겨진 막대로 만들 수 있는 경우 사용되는 막대의 최소 개수를 출력한다.
예제1
입력
56
.*....
.*****
.*....
*****.
.*....
출력
3