Fivestar > 문제은행

본문 바로가기


알고리즘 백트랙킹2

1013 : Fivestar

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 74 회    시도횟수: 723 회   



비어있는 높이 N, 너비 M의 격자 판이 있다(비어있는 공간은 '.'로 표기한다.) 이러한 격자판에 ‘*****’가 새겨진 막대를 이용하여 입력받은 패턴을 재현할 수 있는지 없는지 판단하고, 가능 할 경우 사용되는 막대의 최소 개수를 알아내는 프로그램을 제작하고자 한다. 막대에 새겨진 한 글자와 격자 판의 한 칸의 크기는 일치한다.

 

막대는 격자 판 내에 놓여야 하며, 수는 제한이 없다. 막대끼리 겹칠 수 있으며, 수직으로, 수평으로만 놓을 수 있다. 아래와 같은 패턴이 입력되었을 경우 2번째 열에 수직으로 막대를 하나, 2번째 행에 두 번째 열에 수평으로 막대를 하나, 마지막으로 4번째 행 첫 번째 열에 수평으로 막대를 하나 놓게 되면 3개의 막대로 패턴을 완성시킬 수 있다.

 

.*....
.*****
.*....
*****.
.*....

 


첫줄에는 격자판의 높이 N 너비 M이 입력된다(1≤N≤5, 1≤M≤10). 그 다음 줄부터 N x M 크기의 패턴이 입력된다. 비어있는 칸은 ‘.’로 채워져야 하는 칸은 ‘*’로 표시한다.



입력된 패턴을 만들 수 없을 경우 -1을 0개 이상의 "*****"가 새겨진 막대로 만들 수 있는 경우 사용되는 막대의 최소 개수를 출력한다.


[Copy]
5 6
.*....
.*****
.*....
*****.
.*....
[Copy]
3




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.