Problem1453--百步穿杨

1453: 百步穿杨

[Creator : ]
Time Limit : 0 sec  Memory Limit : 256 MB

Description

Stella 是一个神箭手,不过并不是他自己射箭——在一块 N×M N \times M N×M 的方格空地上有些地方摆有箭塔,其他还有地方有箭靶。每个箭靶有不同的分值,而箭塔的方向为上下左右其中一种,Stella 通过控制箭塔选定目标,然后一起发射击中这些箭靶获取其分数来展现自己的「射箭」技术。现在你需要计算在给定的空地上,Stella最多能获得多大的分数。

相关的限制如下:

  1. 每个箭塔原则上可以选择所指方向上任意一个箭靶,当然也可以选择不攻击。
  2. 为保证正常运行,每个箭塔的攻击范围中不会有其他箭塔。
  3. 同样为确保正常攻击,所有箭塔的攻击轨迹在地面的投影不能在任意格子相交。

输入格式

第一行两个整数 N,M N, M N,M
接下来 N N N 行每行 M M M 个字符,表示每个格子的状态:

  1. .”表示空地。
  2. A”、“V”、“<”、“>”分别表示朝向上下左右的箭塔。
  3. 1”~“9”分别表示得分为 1 1 19 9 9 的箭靶。

输出格式

输出一行一个整数,表示最大得分。

样例

样例输入 1

3 4
.9V.
>..7
.A1.

样例输出 1

10

数据范围与提示

对于 30% 30\% 30% 的数据,N,M≤5 N, M \le 5 N,M5
对于 100% 100\% 100% 的数据,N,M≤50 N, M \le 50 N,M50

Source/Category