题目描述

费尽周折，终于将众将士的残骸运送到了 KD 军事基地地底层的大型墓地入口。KD 的伙伴和战友们都参加了这次重大的送葬仪式。右边是一扇敞开的大门，进去便是墓地了，左边是一堵凹进去的墙，没有什么特别的地方。

部队缓缓进入右边的门，一切，就这么结束了么……

此时， F 却没有跟上队伍，在一般 MM 都会有的强烈的第六感之下，她来到了左边这堵墙前一探究竟。扫去了重重的灰尘之后，墙上一块凹进去的手掌印清晰可见了。F 试着用自己的手对上去，竟刚好合适。稍微用力一按，顿时一声巨响，地上马上裂开一大洞，F 和那厚重的墙瞬间一起落入深渊！当其他人听见了巨大的声响而赶来的时候，一切都恢复平静了。只有那堵墙后面的世界，震惊了所有生物。这到底是什么，为什么会在墓地里面？

墙的后面是一个巨大的迷宫！简单的一行字浮现在了一侧的墙上：猛烈撞击所有发亮的机关石。当大伙好奇的蜂拥进迷宫的时候，一块莫名其妙的巨石竟从入口上方落下，将入口完全堵死了！石头上清晰的写了一行字：超过规定时间不能完成任务，全部人都会困死于此。看来，只有硬着头皮去闯，才有可能离开这里，并且探索出这个迷宫的秘密了。

于是大家马上散开，很快摸清了这里的地形，剩下的任务就是轰击石头了。那么……论攻击力最高的，自然非功夫 DP 莫属，而且功夫 DP 可以使用前滚翻移动法，能够瞬间获得巨大的初速度，并且在直线运动的时候速度将近似光速，质量无穷大，那动能自然就……DP 每次可以选择朝一个方向滚动，并且可以自己选择在某位置停下来，或者撞击到墙和石头的时候被迫停下来。由于直线速度过快，所以要停下来拐弯自然就是很麻烦的事情。那么只有制定出一个最好的运动方法，使得 DP 停下来次数最少，才能争取尽量多的时间！

输入格式

第一行 $3$ 个正整数 $N$、$M$ 和 $T$。表示这是一个 $N \times M$ 的迷宫，并且有 $T$ 个机关石。

接下来用一个 $N\times M$ 的字符矩阵描述迷宫，. 表示是空地，# 表示是墙。

接下来 $T$ 行每行 $2$ 个正整数 $X,Y$，描述一个机关石的位置，它在迷宫对应的位置是 #。不会有两个机关石在同一位置。

最后一行 $2$ 个正整数 $X_0,Y_0$，表示 DP 的初始位置。

输出格式

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

样例输入

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

样例输出

5

提示

数据规模：

对于 $10\%$ 的数据，$N,M\leq 10,T\leq 2$；

对于 $40\%$ 的数据，$N,M\leq 50,T\leq 10$；

对于 $100\%$ 的数据，$N,M\leq 100,T\leq 15$。

注意事项： 迷宫的最外层是墙，即任何时候不可能滚出迷宫，墙是撞不烂的（好硬）！

每次 DP 只能选择 $4$ 个基本方向中的一个方向移动，每块机关石都必须被撞击，撞击后变成普通的墙。

题目来源

HNOI2009 集训 Day8。