时间限制: 1000ms
空间限制: 262144kB

题目描述

最近探险家们在X国发现了一处遗迹，里面的地形复杂好比一个迷宫，但是里面有非常多的宝藏。探险家们提前用“鹰眼”探查到了这个迷宫的地图结构，可以用一个二维图来表示。#代表无法跨越的陷阱，*代表可以去的位置，某些位置上存在宝藏，用一个数字表示这个宝藏的价值。遗迹特别神奇，某个位置一旦经过就会消失，不可再次到达。在迷宫中移动有上下左右四种方式。探险家们想要知道从左上角的入口到达右下角的出口，最多可以获得多少宝藏？

输入格式

第一行包含两个整数 $n,m$，表示迷宫的大小。接下来的$n$行，每行包含$m$个字符，代表迷宫（保证入口没有陷阱）。

输出格式

一个整数。代表总共可获得的宝藏价值和，无法到达出口则输出-1

样例

Input 1

5 6 
1****# 
*###2# 
4###*# 
*###1# 
**1***

Output 1

6

样例解释

这个测试样例中，一种可行的路径是：从$(1,1)$位置开始，向下，向下，向下，向下，向下，右移，右移，右移，右移，右移，到达$(5,6)$位置。在这个路径中，可以获得的宝藏价值是$1+4+1=6$。

数据范围

$1 <= N，M<= 7，0<=宝藏价值<=9$

求找原题玄一关，找到了踢踢我