题目描述

给出一个地图（网格），格子分为空地，草地，墙壁。

要在空地上放能向上下左右 4 个方向发射激光的机器人。

墙壁能挡住激光，草地不能挡住激光也不能放机器人。

在机器人不能互相打到对方的情况下，最多放置多少个机器人。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数$m$ 和$n$，表示地图的大小为$m$ 行$n$列。

接下来 m 行，每行包含$n$个字符，用来描述整个地图。

# 代表墙壁，* 代表草地，o 代表空地。

输出格式

每组测试数据在第一行输出 Case :id，id 是数据编号，从 1 开始。

第二行包含一个整数，表示机器人的个数。

样例

2
4 4
o***
*###
oo#o
***o
4 4
#ooo
o#oo
oo#o
***#

Case :1
3
Case :2
5

数据范围

$1≤m,n≤50$

来源

• 算法竞赛进阶指南