s02162. 带权迷宫 未做

一个 $n\times m$ 的网格，每格有一个通过代价（数字 $1\sim 9$），# 表示不可通行。从 $(1,1)$ 走到 $(n,m)$，每次向上、下、左、右走一格。路径代价 = 经过格子的代价之和（含起点与终点）。求最小代价。数据保证 $(1,1)$ 能到达 $(n,m)$。

第一行两个整数 $n,m$。接下来 $n$ 行，每行 $m$ 个字符（数字 $1\sim 9$ 或 #）。

一行一个整数，最小路径代价。

• 对于 30% 的数据：$n,m\le 10$
• 对于 60% 的数据：$n,m\le 100$
• 对于 100% 的数据：$n,m\le 1000$