在一个 10x10 矩阵中的某些格子上分布着宝物,某人从一处像贪吃蛇一样开始吃,但不会像贪吃蛇一样长身体,而且必须连续吃宝物才可以前进。前进方向 8 个相邻格子都可以,怎样的算法可以选择一条吃掉最多宝物的路线?
我现在用递归做,但是碰到那种 4x4 以上连续宝物的地图就会超时。。。
求高手解答~
__
// gamemap 由 info矩阵 构成, 每个info 包括一个坐标pos 和一个data。data 是str ,代表宝物的种类
// from info pos , get the longest way with same color
private List<Pos> getLongest(MapInfo info, GameMap map, List<Pos> oldList)
{
List<List<Pos>> lists = new LinkedList<>();
boolean found = false;
// 遍历相邻节点,递归调用
for (MapInfo nearInfo : GameUtil.getNearInfos(info.getPos(), map))
{
if (info.getData().equals(nearInfo.getData()) && !oldList.contains(nearInfo.getPos()))
{
found = true;
List<Pos> tmpList = new LinkedList<>(oldList);
tmpList.add(nearInfo.getPos());
tmpList = getLongest(nearInfo, map, tmpList);
lists.add(tmpList);
}
}
if (!found)
{
return oldList;
}
// 返回最长的那个
return lists.stream().max(Comparator.comparingInt(List::size)).orElse(null);
}
[input]( http://www.jianshu.com/p/4a4e74755feb )
{"moves":[{"x":1,"y":1},{"x":0,"y":1},{"x":0,"y":2},{"x":0,"y":3},{"x":1,"y":3},{"x":1,"y":2},{"x":2,"y":1},{"x":3,"y":0},{"x":3,"y":1},{"x":4,"y":0},{"x":5,"y":0},{"x":6,"y":0}]}
1
bjrjk 2017-09-17 16:02:50 +08:00 via Android 1
加个记忆化搜索就行了,或者动态规划也行,稍后我写个代码放上来吧,有题目链接吗?
|
2
starvedcat 2017-09-17 16:04:52 +08:00
“连续吃宝物才可以前进”是什么意思?
|
3
hqtc OP @starvedcat 就是字面意思啊,每次前进必须吃到东西啊,不能走空地。
|
4
helica 2017-09-17 16:17:36 +08:00 via iPhone
这不是 poj 那道滑雪吗
|
7
hqtc OP @helica google 了一下找到了。。http://poj.org/problem?id=1088, , 的确是一个意思
|
9
bjrjk 2017-09-17 16:38:19 +08:00 via Android
@hqtc https://renjikai.com/luogu-p1434/ 送给楼主一个之前自己写过的化学的题解,c++版本的。
|
10
victor97 2017-09-17 16:42:17 +08:00 via Android
滑雪那道题可以看作是有向无环图,楼主的题意应该是无向有环图啊?这类图求最长路好像是 NP 问题。
|
14
messyidea 2017-09-17 18:00:36 +08:00 1
好像可以用网络流做
建一张图。添加 4 个点 S,s,T,t S->s 流量为 1,费用为 0 t->T 流量为 1,费用为 0 s->所有有食物的格子,流量为 1,费用为 1 所有有食物的格子->t,流量为 1,费用为 0 所有有食物的格子->它能走到的有食物的格子,流量为 1,费用为 1 然后跑一下 S->T 最大费用最大流貌似就好了 路径的话 dfs 统计一下有流量的边就可以了 |