逛庙会

题目背景

本题时限3s,请考虑常数优化或者读入优化。(std没有特别进行优化)

题目描述

城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向H个摊位、东西向W个摊位组成的大型方阵。从北开始第i行、西开始第j列的一个摊位,我们表示为(i,j)。 正妹现在处于庙会的(1,1)位置,然后要往东或者往南走,一直走到(H,W)跟八尾勇汇合。(1,1)点和(H,W)和它们的东西南北邻近一个摊位都没有开张。别的地方也可能有一些摊位没有开张。 正妹是个吃货。只要到达一个摊位,总是经不起小吃的诱惑。如果这个摊位开张了,而且该摊位小吃还没有买过,就会买下这个摊位的小吃。无论这个摊位是否有开张,其东西南北直接相邻的摊位小吃的香味也很诱人,如果邻近的摊位的小吃没有买过,那么就在这些邻近(上下左右)的且没有买过的摊位(假设有r个)中,买其中的r-1个摊位的小吃。然后继续往东或者南走。同一家小摊,不会购买多次。 虽然正妹是个吃货,但是零用钱还是很有限。可是她又是管不住自己,就是要买买买。所以她希望知道自己最少能吃掉多少钱的东西。

输入输出格式

输入格式


第一行2个数,H,W 接下来H行,每行W个字符串,**没有空格隔开**,是1-9或者'.'中的一个,表示价格,一个点表示没有开张。

输出格式


一个整数,表示最少花掉的钱

输入输出样例

输入样例 #1

5 5
....7
.21.8
9346.
..45.
.8...

输出样例 #1

9

说明

```cpp 样例解释:o为正妹经过的路线,x为她顺便买的小吃。当走到(2,4)时,左下右都有开张且没有买过的摊位,于是买左和右,继续沿着路线走。由于之后路线没有经过没有买过摊位,而且上下左右开张且没买过的摊位不超过1,所以一个都不买了。 5 5 oooo7 .2xoo 9346o ..45o .8..o ``` 20%数据,开张的摊位不超过20 100%数据, (3 ≦ H ≦ 1000, 3 ≦ W ≦ 1000) 特别注意:数据是在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.. } } ```