芯片难题 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