D. 칩 챌린지

한 유명 마이크로프로세서 회사가 자사 컴퓨터 칩 일부에 교체 가능한 부품(위젯)을 배치하는 일에 당신의 도움을 요청했다. 각 칩의 설계는 \(N \times N\) 정사각형 모양의 슬롯 배열이다. 슬롯 하나에는 부품 하나를 넣을 수 있고, 가능한 한 많은 위젯을 넣는 것이 목표이다. 물론 현대 프로세서 설계는 복잡하다. 안타깝게도 몇 가지 제한이 있다.

• 일부 슬롯은 비활성화되어 있다.

• 일부 슬롯은 이미 다른 부품이 차지하고 있어 위젯에 사용할 수 없다.

• 칩의 가로·세로 가장자리에는 형제 메모리 버스가 연결되어 있고, 이들의 대역폭 부하가 일치해야 한다. 따라서 첫 번째 행과 첫 번째 열의 부품 수가 정확히 같아야 하고, 두 번째 행과 두 번째 열도 같아야 하며, 이하 마찬가지이다. 부품 수에는 칩에 이미 놓여 있는 부품과 추가되는 위젯이 모두 포함된다.

• 마찬가지로 각 행과 열의 끝에는 전원이 연결되어 있다. 과열 지점을 피하기 위해, 어떤 행이나 열도 주어진 \(A\)와 \(B\)에 대해 칩 전체 부품 수의 \(A/B\)를 넘게 가질 수 없다. 칩의 명세는 \(N\)개의 줄에 각 \(N\)개의 문자로 주어지며, ‘.’은 빈 슬롯, ‘/’은 비활성화된 슬롯, ‘C’는 이미 부품이 차지한 슬롯을 나타낸다. 예를 들어 CC/.. ./.// ..C.C /.C.. /./\(C/ If\) — 어떤 행이나 열도 부품의 \(3/10\)을 넘게 가질 수 없다면, 이 \(5 \times 5\) 칩에 추가할 수 있는 위젯의 최대 개수는 7이다. 가능한 배치는 아래와 같으며, ‘W’는 빈 슬롯에 추가된 위젯을 나타낸다. \(CC/W\). \(W/W\)// W.C.C /.C\(WW /W/C\)/

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 세 정수, 즉 칩의 크기 \(N\) (\(1 \le N \le 40\))과 위에서 설명한 \(A\), \(B\) (\(1 \le B \le 1000\), \(0 \le A \le B\))가 있는 줄로 시작한다. 다음 \(N\)개의 줄에는 슬롯을 설명하는 \(N\)개의 문자가 주어지며, 각 문자는 위에서 설명한 ‘.’, ‘/’, ‘C’ 중 하나이다. 마지막 테스트 케이스 다음에는 0 세 개가 있는 줄이 주어진다.

각 테스트 케이스마다 케이스 번호로 시작하는 한 줄을 출력한다. 해가 있으면 칩에 추가할 수 있는 위젯의 최대 개수를 출력한다. 해가 없으면 “impossible”을 출력한다. 샘플 출력의 형식을 따른다.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2011