「题目背景」
小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫,一旁的木牌上写着:“你可以回头,但你永远无法离去。”
「问题描述」
木牌下方有一行小字:“撞击所有机关墙”。
G-1500机器人每次可以朝着前方光速移动,质量、动能无穷大,可以选择自己在行进中停下来或者撞墙后停下来,移动时只有转向需要花费时间。
真是个诡异的迷宫,不过,小奇的眼前已经出现了迷宫的地图,它想尽早离开这里,请你帮助小奇制定一个行动方案,使得转向的次数最小,且在行动时撞击过所有的机关墙。
第一行包含三个正整数n,m,K,表示迷宫的大小为n*m,迷宫中有K个机关墙。
接下来给出一个n*m的矩阵,.表示空地,#表示墙。
接下来K行,每行包含两个正整数a,b,表示第a行第b列的墙是机关墙。
最后一行包含两个正整数x,y,表示小奇的起始位置在第x行第y列,为了方便,认为起始时机器人方向奇怪,需要转向一次。
输出一个正整数,表示小奇撞击完机关墙的最少转向次数,保证问题有解。