问题 H: “黑化”的李华之疯狗咬人计划

问题 H: “黑化”的李华之疯狗咬人计划

时间限制: 1 Sec  内存限制: 128 MB
提交: 84  解决: 33
[提交][状态][讨论版][命题人:]

题目描述

众所周知,李华是一个勇敢、机智的寻宝家。在最终的收官之战中,他找到了宝藏,但没料到,宝藏才是最大的危机,找到宝藏后的李华性情大变,他变得邪恶、狠毒,一步步“黑化”了。。。。。。


邪恶的李华有多条疯狗,疯狗见到人就会咬(但不会咬到李华),这天,李华带着他的疯狗大军来到了一片广场上,广场上有人,李华便制定了一个疯狗咬人计划,现在请你计算李华的疯狗最多能咬伤多少人。


 假设现场用一个矩阵表示,李华有多条疯狗,现场的人也有多个可能。
例子:
#p.d#p#
#####.#
d……..#
######p
d表示疯狗,p表示人,点表示可以通行的路,#表示石头挡住的路,不能通行。
疯狗只能上下左右走,不能越过障碍物。
上面的那个例子疯狗最多可以咬到2个人。因为第三个人被四周包围疯狗无法到达。

输入

输入数据有多组。每组两个整数R,C, 2=<R,C<=100, R表示矩阵的行数,C表示矩阵的列数,然后输入相应矩阵,矩阵保证有疯狗和人。当输入R=0且C=0时候输入结束。

输出

输出疯狗最多能咬多少人的数量。

样例输入

4 7
#p.d#p#
#####.#
d.....#
######p
0 0

样例输出

2

提示

[提交][状态]