면적 러그
면접 대비시간 제한2초메모리 제한512 MB
n×n 격자에서 s×s 러그를 놓을 수 있는 모든 위치마다 덮이는 더러운 칸 수를 세어, 개수별 경우의 수를 오름차순으로 출력한다.
문제
집의 주된 방은 한 변의 길이가 n피트인 정사각형이다. 안타깝게도 바닥이 더럽다. 당신은 대학생이라 청소를 몹시 싫어한다. 청소를 하는 대신, 더러운 부분 일부를 가리기 위해 한 변의 길이가 s피트인 정사각형 면적 러그를 산다.
n×n 크기의 방에 s×s 크기의 면적 러그를, 모든 s×s 평방피트가 바닥의 일부를 덮도록, 회전 없이 축에 맞추어 놓는 모든 방법을 생각하자. 특정 개수의 더러운 부분을 가리는 방법은 몇 가지인가?
입력은 단일 테스트 케이스로 이루어진다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다.
각 테스트 케이스의 첫 줄에는 두 정수 n (1 ≤ n ≤ 1,000)과 s (1 ≤ s ≤ min[n,100])가 공백으로 구분되어 주어진다. n은 방 한 변의 길이이고, s는 새 면적 러그 한 변의 길이이다.
다음 n개의 줄에는 정확히 n개의 문자로 이루어진 문자열이 주어진다. 각 문자는 바닥의 깨끗한 부분을 나타내는 ‘C’ 또는 더러운 부분을 나타내는 ‘D’이다.
가려진 더러운 바닥 부분의 개수마다, 0부터 s2까지, 크기 s×s인 면적 러그로 그만큼의 더러운 부분을 가리는 방법의 수가 0보다 크면, 더러운 부분의 개수와 그 개수를 가리는 방법의 수를 한 줄에 공백으로 구분하여 출력한다. 더러운 부분의 개수가 작은 것부터 큰 것 순서로 출력한다.