7961: BZOJ3961：[WF2011]Chips Challenge

一位著名的微处理器公司邀请您帮忙在他们的电脑芯片上安排一些组件，每个芯片被设计成拥有N × N个插槽的正方形。一个插槽可以存放一个组件，你要尽可能多地在芯片上安装组件。 现代的处理器设计是相当复杂的。不幸地，你需要满足以下的限制。 * 一些插槽是不可用的 * 一些插槽已经被其他的组件所占据，无法用于固定额外的组件。 * 芯片水平和垂直边界上连接着着一些内存总线,他们的带宽负载需要匹配。也就是说，第一行和第一列的组件数目必须一样多，第二行和第二列的组件数目必须一样多，依此类推。这里的组件数要包括之前已经存在于芯片之上和后来加上去的。 * 类似地，每行每列都有能量供应系统。为了避免局部过热，对于给定的一组A，B，任何一行/一列的组件数都不能超过总组件数的A / B。 你希望计算出最多可以在芯片上再安装多少个组件。

输入格式

对于每组数据，第一行包括三个正整数N，A，B。 接下来包含 N 行,每行包含 N 个字符，表示了描述芯片的矩阵。其中 '.' 表示可用插槽，'/' 表示不可用插槽，'C'  表示插槽已被一个部件占据。整个测试以"0 0 0"表示结束

输出格式

如果有解，输出一行包括一个正整数，表示最多能再安装多少个组件。 否则，输出"impossible"（不包含引号）。

样例输入

2 1 1
/.
//
2 50 100
/.
C/
0 0 0

样例输出

Case 1: 0
Case 2: 1

提示

1 ≤ N ≤ 40，1 ≤ B ≤ 1000， 0 ≤ A ≤ B。

题目来源

没有写明来源