P2238.md

逛庙会

题目描述

城市里正在举行庙会。庙会里有很多摊位。庙会的会场是一个南北向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

样例输入 #1

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

样例输出 #1

9

提示

样例解释：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）：

    for (i = 0; i < H; ++i) {
        scanf("%s", in);
        for (j = 0; j < W; ++j) {
            shop[i][j] = blabla..
        }
    }