← 返回题目列表

Codeforces · 1505/E

E. 小菜一碟

中文机器翻译题面 查看原题

一只老鼠遇到了一个漂亮的大蛋糕,决定在上面散步,并在途中吃掉蛋糕顶部的浆果。蛋糕呈长方形,整齐地分成正方形;有些方块里有浆果,有些则没有。

不过,老鼠有点着急,所以一旦她从西北角(输入数据中的左上角单元格)进入蛋糕,她只会向东(右侧)或向南(向下)移动,直到到达东南角(右下角单元格)。她会吃掉她经过的方格中的所有浆果,但不会吃掉其他方格中的浆果。

老鼠尝试选择自己的路径,以便最大限度地消耗浆果数量。然而,她的匆忙和饥饿可能会影响她的判断,导致她做出次优的决定……

输入

输入的第一行包含两个整数 $$$H$$$ 和 $$$W$$$ ($$$1 \le H, W \le 5$$$),用空格分隔,即蛋糕的高度和宽度。

接下来的 $$$H$$$ 行每行包含一个由 $$$W$$$ 字符组成的字符串,代表该行中蛋糕的方块:“.”代表一个空的方块,“*”代表一个有浆果的方块。

输出

输出老鼠按照她的策略将吃掉的浆果数量。

示例

输入 #1

4 3
*..
.*.
..*
...

输出 #1

3

输入 #2

4 4
.*..
*...
...*
..*.

输出 #2

2

输入 #3

3 4
..**
*...
....

输出 #3

1

输入#4

5 5
..*..
.....
**...
**...
**...

输出#4

1