芯片难题 Chips Challenge

题意翻译

作为芯片设计的一部分,你需要在一个$N * N (N <= 40)$的网格里放置部件。其中有些格子里已经放了部件(用$C$表示)还有些格子不能放部件(用 "/" 表示),剩下的格子需要放置尽量多的新部件(用$W$表示)。 要求对于所有的$1 <= x <= N$,第$x$行的部件个数($C$与$W$的和)等于第$x$列的部件数。为了保证散热,任意行或列的部件数不能超过整个芯片总部件的$A / B$。如图放了7个新部件。 CC/.. CC/W. ./.// W/W// ..C.C W.C.C /.C.. /.CWW /./C/ /W/C/ (a) (b)

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3545 [PDF](https://uva.onlinejudge.org/external/11/p1104.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

输入样例 #1

2 1 1
/.
//
2 50 100
/.
C/
2 100 100
./
C.
5 3 10
CC/..
././/
..C.C
/.C..
/./C/
5 2 10
CC/..
././/
..C.C
/.C..
/./C/
0 0 0

输出样例 #1

Case 1: 0
Case 2: 1
Case 3: impossible
Case 4: 7
Case 5: impossible