提示: 欢迎访问OurACM平台。
Problem 2225 小茗的魔法阵

Accept: 36    Submit: 106
Time Limit: 2000 mSec    Memory Limit : 65536 KB

Problem Description

在打败了易基•普罗布朗、诺姆•普罗布朗之后,小茗同学开始挑战哈德•普罗布朗。

一番交战之后,哈德展开了一大波攻击。小茗同学为了抵御攻击,一边放魔法阵一边放魔法阵,然后他也不知道自己一共放了几个魔法阵。回收魔法阵是需要花费时间的,为了抵御下一波攻击,小茗同学需要知道自己共放了几个魔法阵,由于情况紧急,这个任务需要由你来完成。

魔法阵是三角形△的,比如

.............

.x..x....x...

...xxx..x.x..

.......xxxxx.

.............

以上都认为是魔法阵。

(即:三角形三个顶点为(i,j),(i+k,j-k),(i+k,j+k),边上均为’x’。三角形中间的元素没有要求。一个’x’可以同时属于多个魔法阵。单个’x’也算一个魔法阵。)

场地可以认为是一个N×M的矩形,每个位置上为’.’表示没有东西,或’x’表示有魔法阵。

Input

第一行是一个整数T(T<=10),表示共有T组测试数据。

每组数据的第一行包含两个整数N M(N,M≤1000),表示矩阵大小。

接下来N行 ,每行M个字母为‘.’或者‘x’。

Output

每组数据输出独占一行,输出格式为”Case #x: y”,x从1开始,表示数据组号,y表示相应的魔法阵的数量。

Sample Input

1 3 3 .x. xxx ...

Sample Output

Case #1: 5

Source

FOJ有奖月赛-2016年4月(校赛热身赛)

Submit  Back  Status  Discuss