小奇走迷宫
题号:NC212449
时间限制:C/C++/Rust/Pascal 10秒,其他语言20秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

「题目背景」

小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫,一旁的木牌上写着:“你可以回头,但你永远无法离去。”

「问题描述」

木牌下方有一行小字:“撞击所有机关墙”。

G-1500机器人每次可以朝着前方光速移动,质量、动能无穷大,可以选择自己在行进中停下来或者撞墙后停下来,移动时只有转向需要花费时间。

真是个诡异的迷宫,不过,小奇的眼前已经出现了迷宫的地图,它想尽早离开这里,请你帮助小奇制定一个行动方案,使得转向的次数最小,且在行动时撞击过所有的机关墙。

输入描述:

第一行包含三个正整数n,m,K,表示迷宫的大小为n*m,迷宫中有K个机关墙。

接下来给出一个n*m的矩阵,.表示空地,#表示墙。

接下来K行,每行包含两个正整数a,b,表示第a行第b列的墙是机关墙。

最后一行包含两个正整数x,y,表示小奇的起始位置在第x行第y列,为了方便,认为起始时机器人方向奇怪,需要转向一次。

输出描述:

输出一个正整数,表示小奇撞击完机关墙的最少转向次数,保证问题有解。
示例1

输入

复制
4 6 3

……

.#..#.

.#…#

….#.

2 2

3 6

4 5

1 5

输出

复制
6