题面描述

小青被关在了迷宫里，迷宫里有许多金币。小青一开始在迷宫的最左上角$(1,1)$请你帮小青找到以下问题的答案：

​ 1.小青能否从迷宫走出去

​ 2.小青最多能捡多少金币。

tips

如果你不会BFS模板，请查看笔记而不是不写这道题

输入

第一行输入一个整数$n$，代表迷宫的大小为$(n * n)$。$(1\leq n \leq 10^3)$

第二行输入两个整数 $x,y$，代表出口。$(1\leq x,y \leq n)$

接下来的$n$行，每行有$n$个字符，代表地图。其中:

​ $'\#'$ 代表【墙】，不能走;

​ $'.'$ 代表【路】，可以走;

​ $'\$'$ 代表【金币】。

​ 题目保证出口与入口$(1,1)$为【路】。

输出

一个整数，代表最多捡到的金币数量。如果迷宫无法出去，则输出$-1$。

样例输入 1

5
5 5
.$...
.###$
.#$#.
.###.
.$.$.

样例输出 1

4

样例解释 1

出口为 (5,5)，小青可以从左上角沿着迷宫外围走到出口。

地图中共有 5 个金币，其中 (3,3) 的金币被四周的墙围住，无法到达。

其余 4 个金币位置分别为：

(1,2), (2,5), (5,2), (5,4)

它们都可以在到达出口前被捡到，所以答案为 4。

样例输入 2

4
4 4
..$.
####
$#..
.#..

样例输出 2

-1

样例解释 2

第二行全是墙，导致起点所在区域和出口 (4,4) 所在区域完全隔开。

虽然小青可以捡到 (1,3) 的金币，但她无法走到出口，因此输出 -1。

样例输入 3

1
1 1
.

样例输出 3

0