寻宝

题目描述

侠盗 Hank 经过千难万险终于来到了恶人岛，为了拿到恶人岛的宝座去帮助穷人，Hank 先对恶人岛进行了侦查，发现恶人岛有一个迷阵，宝藏摆在了迷阵的深处。迷阵由 $M \times N$ 个方格组成，有的方格内有可以发现 Hank 的守卫，而有的方格内则是安全。为了展现自己的实力，Hank 决定不仅要拿走恶人岛的宝藏，还要给他们留一封信，告诉恶人自己有 $g$ 种方法找到宝藏。现在要求你来帮助他实现这个目标。

迷阵越大，守卫越多。

输入格式

输入有一组测试数据，以两个非零整数 $N$ 和 $M$ 开始，两者均不大于 $20$。$N$ 表示迷阵行数，$M$ 表示迷阵列数。接下来有 $N$ 行，每行包含 $M$ 个字符，不同字符分别代表不同含义：

1. @：Hank 所在的位置；
2. .：可以安全通行的方格；
3. #：有守卫的方格；
4. *：宝藏所在位置。

输出格式

一个整数 $g$，表示 Hank 有 $g$ 种方法可以找到宝藏。如果他不可能找到宝藏，则输出 $-1$。

样例输入 #1

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###

样例输出 #1

4

样例输入 #2

9 6
.#..#.
.#.*.#
.####.
..#...
..#...
..#...
..#...
#.@.##
.#..#.

样例输出 #2

-1

数据范围

• $1 \le N, M \le 20$；
• 迷阵中的字符只包含 @、.、#、* 四种。

知识点与难度

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

• 时间限制：1000MS
• 内存限制：256MB

测试点分布