5831: 欢乐球球
[Creator : ]
Description
最近小蒜在玩一款名叫欢乐球球的小游戏,游戏中有一根圆柱,圆柱共有 $n$ 层,每层有 $5$ 个位置,围成一个环形,每个位置可以为空 "." 或地板 "#" 或熔岩 "*"。
现在由小蒜操作的小球在最高层 $n$ 层,并开始向下掉落。如果当前的位置为空 "." 时,小球只能向下掉落,并获得 $k$ 分,$k\ (k≥1)$ 为目前连续掉落的高度,每次可以掉落 $1$ 层,但是在掉落的过程中(在两层中间时)可以选择向左或向右移动一个位置,当然也可以不移动,直接掉落到下一层的相同位置;若当前为地板 "#" 时,可以选择向左或向右移动一步,左右移动不得分;若当前掉落到熔岩 "*" 上时,则游戏结束。
小蒜最初在第 $n$ 层的第一个位置,数据保证第 $n$ 层的第一个位置为地板 "#"。如果小蒜掉落到第 $0$ 层(不存在)则游戏结束。
现在想请你帮助小蒜计算出小蒜这一局最多能获得多少分。
现在由小蒜操作的小球在最高层 $n$ 层,并开始向下掉落。如果当前的位置为空 "." 时,小球只能向下掉落,并获得 $k$ 分,$k\ (k≥1)$ 为目前连续掉落的高度,每次可以掉落 $1$ 层,但是在掉落的过程中(在两层中间时)可以选择向左或向右移动一个位置,当然也可以不移动,直接掉落到下一层的相同位置;若当前为地板 "#" 时,可以选择向左或向右移动一步,左右移动不得分;若当前掉落到熔岩 "*" 上时,则游戏结束。
小蒜最初在第 $n$ 层的第一个位置,数据保证第 $n$ 层的第一个位置为地板 "#"。如果小蒜掉落到第 $0$ 层(不存在)则游戏结束。
现在想请你帮助小蒜计算出小蒜这一局最多能获得多少分。
Input
第一行一个数字 $n$,圆柱共有 $n$ 层。
接下来 $n$ 行,每行 $5$ 个字符,第 $i$ 行表示第 $n-i+1$ 层每个位置的情况,每个位置的情况用 "#.*" 三种字符来描述,输入不存在其他无关信息。
接下来 $n$ 行,每行 $5$ 个字符,第 $i$ 行表示第 $n-i+1$ 层每个位置的情况,每个位置的情况用 "#.*" 三种字符来描述,输入不存在其他无关信息。
Output
输出只有一行一个整数,表示小蒜最多能够获得的分数。
Constraints
对于 $30\%$ 的数据,$1\le n \le 10$。
对于 $60\%$ 的数据,$10 < n \le 100$。
对于 $100\%$ 的数据,$100 < n \le 1000$。
对于 $60\%$ 的数据,$10 < n \le 100$。
对于 $100\%$ 的数据,$100 < n \le 1000$。
Sample 1 Input
10
#.**.
..#..
..###
#.###
#.###
#.###
#.###
#.###
.....
.....
Sample 1 Output
55