问题2013--寻宝藏

2013: 寻宝藏

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

解决: 19提交: 36统计

题目描述

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

输入

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

数据范围：1<=n,m<=7 ,  0<=宝藏价值<=9。



输出

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

样例输入 Copy 

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

样例输出 Copy 

6

来源/分类

深度优先搜索 
提交讨论版