海上营救

题目描述

海上巡逻队收到了求救信号，经确认信号由大山号发出，时间就是生命，必须尽快赶到那里。

通过导航卫星的侦测，巡逻队获得了一张海洋图。地图上这块区域划分成 $n \times n$ 个比较小的区域，其中用 '*' 表示岛屿，用 '.' 表示海洋，巡逻队当前在位置 $(1,1)$。船只航行中只能从一个区域移到相邻的 8 个区域。

计算巡逻队最少需要航行的距离。注意：一块区域距离为 1。

输入格式

第一行一个整数 $n$（$n \le 50$），表示海洋图的大小。

下面是一个 $n \times n$ 的海洋图。

最后一行有 2 个不大于 $n$ 的正整数，表示大山号的位置。

输出格式

一个整数，表示巡逻队到大山号的最短距离；无法到达输出 -1。

样例输入 #1

4
....
.**.
..*.
*...
4 4

样例输出 #1

4

数据范围

$n \le 50$。

知识点与难度

本题涉及的知识点从属于 GESP六级（搜索基础、BFS），难度等级：⭐⭐。

测试点分布