SP2324 MARIOGAM - Mario

马里奥生活在一个N x M的迷宫中。在这个迷宫里有硬币砖、怪物、管道和墙壁。每当马里奥在一个硬币砖的位置上，他都会顶这个砖，并得到砖里的硬币（硬币砖在被击中后不会消失或丢失硬币）。当马里奥碰到怪物时，他会失去一条生命。水管就像传送机：每个系统都有一个出口，至少有一个（但可能有几个）入口通向该出口。当马里奥走进水管的入口时，他被传送到水管的唯一出口。走进水管的出口没有事情会发生。最后，马里奥不能走进墙壁。 马里奥决定玩一个游戏。在游戏开始时，他从某个给定位置的三个生命开始，在每个时间步，他查看所有相邻的格子（不包括墙壁），并随机地选择一个相邻格子（如果x在y的正上方、下方、左侧或右侧，则x与y相邻）。如果马里奥在相邻的格子中没有非墙壁的地方，那么他将留在当前位置。当马里奥失去生命或者他不可能收集更多硬币时，游戏就结束了。帮助马里奥计算出他在一次游戏中所能赚取的预期硬币数。

输入的第一行包含N，M（1≤ N、 M≤ 15） ，给出迷宫的大小。下面是N行，每行长度为M个字符。第i行显示迷宫第i行中单元格的内容。马里奥在唯一的格子中以“$”开头（除了保存马里奥之外，它是一个空单元格）。带有怪物的细胞被指定为“！”。带有硬币盒的单元格由0到9（包括）之间的数字表示，这是该硬币砖中的硬币数。每个水管用与“a”和“z”（包括）之间的不同字母相关联。管道系统的入口用小写字母指定，给定管道系统的唯一出口具有相应的大写字母（如入口标记为“c”的管道系统正好有一个出口，且标记为“C”）。迷宫中出现的每个管道系统都保证有一个出口和至少一个入口。字符“#”表示墙，而“.”指定马里奥可以直接穿过的空格子。

如果马里奥收集的预期硬币数量是无限的，则输出-1。否则，输出一个实数，即马里奥在游戏结束前收集的预计硬币数量。您的答案应准确到10 ^-6 的绝对或相对误差范围内 实际答案。您的输出后面应该跟一个换行符。