神探夏洛克之粉色的研究

神探夏洛克之粉色的研究

背景

Only two of us against the rest of the world.
神探夏洛克连载题目之第一章:粉色的研究。(题目顺序不按照时间顺序进行)

描述

可恶的出租车司机又在城市里搜寻杀害目标了。
因为种种原因(请自行观看神夏第一季第一集)夏洛克在街道间追踪出租车司机。
因为城市地形过于复杂,虽然夏洛克能够清晰地记住城市道路的畅通情况,可是他仍然不能预防出租车司机再次杀人的事件。
城市地图中有许多人物是需要重点守护的,一旦他们死亡会引起不可预料的灾害(主要是Mycroft怕自己的跟班被干掉了),因此需要安排若干个保镖保护他们,每个保镖可以保护在自己正前方的所有重要人物,保镖可以面向上下左右四个方向,且保镖是不会被干掉的。
夏洛克给你了城市的地图,其中带'*'的是重点人物,'.'是空地,'#'是障碍物。
保镖可以安置在除了障碍物的任意位置。
由于英国军情6处财务紧急,他们需要知道最少安排多少个保镖可以保护所有重要人物。
你只需要输出保镖个数,聪明的夏洛克自然知道如何安排所有保镖。

格式

输入格式

第一行包含两个正整数,表示地图的行数n与列数m。(1<=n,m<=100)
接下来n行,每行包括m个字符,表示地图的信息。(具体见题目描述)

输出格式

若能够保护所有重点人物,输出保镖个数。
否则输出"Poor Mycroft will lose his subordinates again!"。

样例1

样例输入1

4 5
.**..
.*#*.
.#*..
..*..

样例输出1

4

样例解释1

原图

方案如下

样例2

样例输入2

4 6
......
.*#*..
..#...
.*#*..

样例输出2

2

样例解释2

原图

方案如下

限制

每个测试点1s

提示

建议不要使用getchar读入字符

后记

夏洛克成功帮助了Mycroft保护了所有重要人物,可是游戏没有结束,夏洛克似乎发现了案件间隐约的联系,难道有幕后主使?

来源

Bill_Yang改编自uva12549,神探夏洛克系列第一章