2864: Skier

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:11 解决:0

题目描述

Jacky888用PyGame制作了一款名叫Skier的小游戏,游戏在平面直角坐标系的第一、二象限进行,$x$轴范围为$[-M,\; M]$,$y$轴范围为$[0,\; N]$。每一个整数点上都可能会有一棵树(#),一个旗帜(*),或是什么都没有(.)。撞到树会扣除50分,而吃到旗帜可以增加10分。一名滑雪者在游戏开始时位于原点,并拥有$7$种状态,编号分别为$-3,-2,-1,0,1,2,3$,表示其每次移动时,y坐标增加1,x坐标增加的值。游戏开始时,其状态为$0$,在每次移动前,玩家可以选择使状态编号$+1$,$-1$,或保持不变,但不能超出$[-3,\; 3]$的范围。同时,skier移动后,x坐标不能超出$[-M,\; M]$的范围,否则该局游戏就会不计成绩。每次移动后,若该点是树,则会扣除$50$分,若该点是旗帜,则会增加$10$分。当skier来到地图顶端,即y坐标等于$N$时,游戏结束。现在Jacky888想知道,对于给出地图的一局游戏,能获得的最大分数是多少?

输入

第一行,两个整数$N$,$M$
接下来$N + 1$行,每行$2 \times M + 1$个数,表示游戏的地图。

输出

共一行,一个整数,表示能获得的最大分数

样例输入 复制

4 4
....*#..#
**..#**..
.....#...
####.####
####.####

样例输出 复制

10

提示

样例解释
一种可行解为:
$y=0$时,状态从$0$变为$0$,移动后坐标变为$(0, 1)$
$y=1$时,状态从$0$变为$0$,移动后坐标变为$(0, 2)$
$y=2$时,状态从$0$变为$1$,移动后坐标变为$(1, 3)$,并获得$10$    分
$y=3$时,状态从$1$变为$2$,移动后坐标变为$(3, 4)$
游戏结束,共获得$10$分

数据范围
对于$30\%$的数据,$0 \le N \le 5,\; 0 \le M \le 3$
对于$100\%$的数据,$0 \le N \le 10^3,\; 0 \le M \le 5 \times 10^2$,保证地图中只含有"*","#",".",且原点处一定为"."