OI题库

【题目描述】

Robert是一位著名的工程师。一天他的老板给了他一个任务。任务的背景如下：

给出一张由方块组成的地图。方块有许多种：墙，草，和空地。老板想让Robert在地图上放置尽可能多的机器人。每个机器人拿着一把激光枪，它可以同时向东西南北四个方向射击。机器人必须一直呆在它开始时被放在的位置并且不断地射击。激光束当然可以经过空地或草地，但不能穿过墙。机器人只能被放在空地上。当然老板不希望看到机器人相互攻击。换句话说，两个机器人不能被放在一条线上（竖直或水平），除非它们中间有一堵墙。

由于你是一位机智的程序员和Robert的好基友之一，他请你帮他解决这个问题。也就是说，给出地图的描述，计算地图上最多能放置的机器人数量。

【输入格式】

输入文件的第一行有两个正整数m,n（1<=m,n<=50），即地图的行数和列数。

接下来有m行，每行n个字符，这些字符是'#','*'或'o'，它们分别代表墙，草和空地。

【输出格式】

输出一行一个正整数，即地图中最多放置的机器人数目。

【样例输入】

sample 1:

4 4

o***

*###

oo#o

***o

sample 2:

#ooo

o#oo

oo#o

***#

【样例输出】

sample 1:

3

sample 2:

5

【提示】

输入输出格式和ZOJ上原题格式有所不同

【来源】

ZOJ 1654 Place the Robots