[ZOJ1654]放置机器人

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file placetherobots.in Output file placetherobots.out

【题目描述】

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