#1556. 墓地秘密

内存限制:64 MiB 时间限制:10 Sec

题目描述

费尽周折,终于将众将士的残骸运送到了KD军事基地地底层的大型墓地入口。KD的伙伴和战友们都参加了这次重大的送葬仪式。右边是一扇敞开的大门,进去便是墓地了,左边是一堵凹进去的墙,没有什么特别的地方。 部队缓缓进入右边的门,一切。。。就这么结束了么。。。。。 此时, F却没有跟上队伍,在一般MM都会有的强烈的第六感之下,她来到了左边这堵墙前一探究竟。扫去了重重的灰尘之后,墙上一块凹进去的手掌印清晰可见了。F试着用自己的手对上去,竟刚好合适。稍微用力一按,顿时一声巨响,地上马上裂开一大洞,F和那厚重的墙瞬间一起落入深渊!当其他人听见了巨大的声响而赶来的时候,一切都恢复平静了。只有那堵墙后面的世界,震惊了所有生物。这到底是什么,为什么会在墓地里面? 墙的后面是一个巨大的迷宫!简单的一行字浮现在了一侧的墙上:猛烈撞击所有发亮的机关石。当大伙好奇的蜂拥进迷宫的时候,一块莫名其妙的巨石竟从入口上方落下,将入口完全堵死了!石头上清晰的写了一行字:超过规定时间不能完成任务,全部人都会困死于此。看来,只有硬着头皮去闯,才有可能离开这里,并且探索出这个迷宫的秘密了。 于是大家马上散开,很快摸清了这里的地形,剩下的任务就是轰击石头了。那么。。。论攻击力最高的,自然非功夫DP莫属,而且功夫DP可以使用前滚翻移动法,能够瞬间获得巨大的初速度,并且在直线运动的时候速度将近似光速,质量无穷大,那动能自然就。。。。。。DP每次可以选择朝一个方向滚动,并且可以自己选择在某位置停下来,或者撞击到墙和石头的时候被迫停下来。由于直线速度过快,所以要停下来拐弯自然就是很麻烦的事情。那么只有制定出一个最好的运动方法,使得DP停下来次数最少,才能争取尽量多的时间!

输入格式

第一行3个正整数N、M和T。表示这是一个N*M的迷宫,并且有T个机关石。 接下来用一个N*M的字符矩阵描述迷宫,.表示是空地,#表示是墙。 接下来T行每行2个正整数X、Y,描述一个机关石的位置,它在迷宫对应的位置是#。不会有两个机关石在同一位置。 最后一行2个正整数X0、Y0,表示DP的初始位置。

输出格式

一个正整数ANS,表示DP至少要停下来多少次才能撞击完所有的机关石。

样例

样例输入


			
4 6 3
……
….#.
…..#
….#.
2 5
3 6
4 5
1 5

样例输出


			
5

数据范围与提示

数据规模:
对于10%的数据,N、M<=10,T<=2;
对于40%的数据,N、M<=50,T<=10;
对于100%的数据,N、M<=100,T<=15;
注意事项:
迷宫的最外层是墙,即任何时候不可能滚出迷宫,墙是撞不烂的(好硬)!
每次DP只能选择4个基本方向中的一个方向移动,每块机关石都必须被撞击,撞击后变成普通的墙。