P2238 逛庙会
题目背景
本题时限 3s，请考虑常数优化或者读入优化。（std 没有特别进行优化）
题目描述
城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向 $H$ 个摊位、东西向 $W$ 个摊位组成的大型方阵。从北开始第 $i$ 行、西开始第 $j$ 列的一个摊位，我们表示为 $(i,j)$。
正妹现在处于庙会的 $(1,1)$ 位置，然后要往东或者往南走，一直走到 $(H,W)$ 跟小 B 汇合。$(1,1)$ 点、$(H,W)$ 点和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。
正妹是个吃货。只要到达一个摊位，总是经不起小吃的诱惑。如果这个摊位开张了，而且该摊位小吃还没有买过，就会买下这个摊位的小吃。无论这个摊位是否有开张，其东西南北直接相邻的摊位小吃的香味也很诱人，如果邻近的摊位的小吃没有买过，那么就在这些邻近（上下左右）的且没有买过的摊位（假设有 $r$ 个）中，买其中的 $r-1$ 个摊位的小吃。然后继续往东或者南走。同一家小摊，不会购买多次。
虽然正妹是个吃货，但是零用钱还是很有限。可是她又是管不住自己，就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。
输入格式
第一行两个整数 $H$ 和 $W$。
接下来 $H$ 行，每行一个长度为 $W$ 的字符串，**没有空格隔开**，是 $1\sim9$ 或者 `.` 中的一个，数字表示价格，`.` 表示没有开张。
输出格式
一个整数，表示最少花掉的钱。
说明/提示
```plain
5 5
oooo7
.2xoo
9346o
..45o
.8..o
```
样例解释：`o` 为正妹经过的路线，`x` 为她顺便买的小吃。当走到 $(2,4)$ 时，左下右都有开张且没有买过的摊位，于是买左和右，继续沿着路线走。由于之后路线没有经过没有买过摊位，而且上下左右开张且没买过的摊位不超过 $1$，所以一个都不买了。
对于 $20\%$ 的数据，开张的摊位不超过 $20$；
对于 $100\%$ 的数据，保证 $3\le H,W\le1000$。
特别注意：数据是在 Windows 生成，输入数据换行符可能是 `\r\n`（两个字符）或者 `\n`。而评测机是 Linux。请特别注意。不接受赛后以「本地能过，评测 WA」的理由申诉。
参考读入方式（节选自 std）：
```cpp
for (i = 0; i < H; ++i) {
scanf("%s", in);
for (j = 0; j < W; ++j) {
shop[i][j] = blabla..
}
}
```