提示: 欢迎访问OurACM平台。
Problem 2199 Patchmania I

Accept: 28    Submit: 108
Time Limit: 1000 mSec    Memory Limit : 65536 KB

Problem Description

农夫Lester破坏了兔子们的家园。你将带领兔子们进行反击。一只叫Calvin的小兔子最喜欢吃萝卜。农田上有一些萝卜,为了尽可能地报复,要把胡萝卜全部吃光。一旦吃起来,完全停不下来。所以,要一口气把萝卜都吃了并立刻逃到洞里。为了防止被农夫发现,要寻找最快的方式吃光所有的萝卜。萝卜吃了就没了。

一口气吃完:当开始吃萝卜时,如果还有萝卜那么下一步一定要吃到萝卜。 吃完萝卜时下一步要跳到洞里。 兔子每一步只能选择上下左右四个方向行走一个格子。

Input

第一行有多组数据。第一行T表示组数。

每组第一行包含n , m , 表示农田的长和宽。(2 <= n , m <= 8)

记下来n行每行m个字符。

X ->Calvin

O ->洞

. –>没有萝卜的土地

# ->有萝卜的土地

数据保证有且仅有一个X和O。

Output

每组先输出 "Case #x: " (其中x为当前组数) 该行接下来输出最短距离和该距离下的方案数。方案数mod 1000000007。如果没有吃完所有萝卜的方案,输出-1。

Sample Input

3 7 5 X.##. ...#. ##### #.#.# #.O.# #...# ##### 2 2 X# #O 3 3 X## ### ##O

Sample Output

Case #1: 22 1 Case #2: -1 Case #3: 8 2

Source

FOJ有奖月赛-2015年10月

Submit  Back  Status  Discuss