提示: 欢迎访问OurACM平台。
Problem 1883 A计划

Accept: 42    Submit: 238
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

特务J接到了一个新任务,代号“A计划”。 

这次组织派她深入Y博士的老巢。那是位于羊驼山的一个地下城,上方有一个特殊的长方体岩石屏障,是进入地下城的唯一突破口。该岩石屏障深度为H,长为L,宽为W,由单位正方体岩石构成。岩石有两种类型,A型岩石是普通岩石,如果下方没有支撑的话则会坠落。B型岩石是特殊岩石,它固定在空间的某个位置不变动,且能够支撑正上方岩石不坠落。

特务J可以从屏障上方任意位置开始行动,且一旦进入屏障区域则只能在其中活动,无法从边界逃脱。她每次可以向前,后,左,右和下方移动,而不能往上移动。遇到A型岩石阻挡时,特务J可以将其爆破,不过她无法伤害B型岩石,

现在给你地下城的岩石屏障的构成图,请你帮她判断下能否突破岩石屏障。

Input

输入第一行有一个整数T,表示有T组数据。

每组输入数据第一行包含三个整数H,L,M(1 <= H,L,W <= 20),表示岩石屏障的深度,长度和宽度。接下来有H部分输入,第i部分表示深度为i的屏障构造。每部分输入有L 行,每行有W个字符。每个字符代表一个单位正方体岩石,‘A’表示这个单位正方体岩石为A型岩石,’B’代表B型岩石。

Output

对于第k组测试数据,首先输出”Case k:”,然后输出为两个整数。首先输出特务J最多能突破几层屏障。其次如果特务J能够突破所有屏障,输出她最少要爆破的岩石数量,否则输出-1。

Sample Input

3 1 2 2 AA AB 4 2 2 AB BB AB BA AA AA BB BA 2 2 2 AA AA BB BB

Sample Output

Case 1:1 1 Case 2:4 7 Case 3:1 -1

Hint

样例2中,特务J可以突破屏障,爆破的岩石有(坐标按(深度,长度,宽度)顺序给出) (1,1,1)->(2,1,1)->(3,1,1)->(3,2,1)->(3,2,2),(2,2,2)->(4,2,2)

Source

wzc

Submit  Back  Status  Discuss