s02167. 地形寻路 未做

一个 $n\times m$ 的网格，每格有一个通行代价（数字 $1\sim 9$）。从 $(1,1)$ 走到 $(n,m)$，每次可以向八个方向移动一格：每移动一格的代价 = 进入格的代价 $+1$；若这一步是对角移动，再额外 $+1$。不允许「斜穿角」：对角移动要求两个相邻的正交格都可通行。求最小总代价（含起点格代价）。

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

一行一个整数，最小总代价。

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