Skip to content

1260: 苦无

题目

题目描述

苦无(Kunai)是一种忍者使用的形状像刀的武器,忍者通过投掷苦无攻击对手。 现在有若干名忍者聚集在一块 H 行 W 列的棋盘式的广场上。每个忍者都站在其所在方块的中心处,任何两个忍者都不在同一个方块上。每个忍者都拿着一个苦无,面朝上 A、下 V、左 <、右 > 四个方向中的一个方向站着。同时广场上同样有着若干敌对势力,每个敌人也都位于一个方块的中心处,标有击杀后的得分。在给定规则之后,你需要输出可能的最大得分。

规则如下: - 每个忍者只能选择面朝方向上的一个敌人投掷苦无,当然也可以选择不攻击。 - 为了防止误伤,所有苦无的飞行路线上不能有其他的忍者,所有苦无的飞行路线(包括起点和终点)不能够相交

输入格式

第一行的输入两个用空格隔开的整数 $H, W$。

对于接下来 $H$ 行,每行 $W$ 个字符,描述了整个广场的初始状态。 1. . 表示一个空地。 2. A, V, <, > 表示这里有一个面向 上/下/左/右 的忍者。 3. 1, 2, 3, 4, 5, 6, 7, 8, 9 表示这里有一个相应分数的敌人。

输出格式

输出一个整数,表示击杀敌人的最大得分

样例输入

样例输入 1

text 4 8 .1.....V ..>...11 ..1...<. .A......

样例输入 2

text 4 8 .....V.. ........ .>..134. ........

样例输出

样例输出 1

text 4

  • 解释如下

text .1.....V .A>>>>11 .A1<<<<. .A......

样例输出 2

text 4 - 解释如下:这个例子存在多解,此时的最大得分是 4,注意这里由于路径不能相交,所以你没有办法同时击杀 3 和 4

text .....V.. .....V.. ........ .....V.. .>>>>>4. .>>>134. ........ ........

数据范围

时间限制:200 ms 空间限制:128 mb

无捆绑测试

  • $(\text{30 points})~ 1 \leq H, W \leq 5$
  • $(\text{70 points})~ 1 \leq H, W \leq 50$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!