这是一个创建于 3136 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目：
在一个 10x10 矩阵中的某些格子上分布着宝物，某人从一处像贪吃蛇一样开始吃，但不会像贪吃蛇一样长身体，而且必须连续吃宝物才可以前进。前进方向 8 个相邻格子都可以，怎样的算法可以选择一条吃掉最多宝物的路线？
我现在用递归做，但是碰到那种 4x4 以上连续宝物的地图就会超时。。。
求高手解答~
__
感觉并不像贪吃蛇的问题，而是找一条最长的连续路径。。。
第 1 条附言 2017 年 9 月 17 日
// 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); } 第 2 条附言 2017 年 9 月 17 日
input 示例
[input]( http://www.jianshu.com/p/4a4e74755feb ) output
{"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 年 9 月 17 日 via Android  1 加个记忆化搜索就行了，或者动态规划也行，稍后我写个代码放上来吧，有题目链接吗？ |
 | 2 starvedcat 2017 年 9 月 17 日 “连续吃宝物才可以前进”是什么意思？ |
 | 3 hqtc OP @starvedcat 就是字面意思啊，每次前进必须吃到东西啊，不能走空地。 |
 | 4 helica 2017 年 9 月 17 日 via iPhone 这不是 poj 那道滑雪吗 |
| 7 hqtc OP @helica google 了一下找到了。。http://poj.org/problem?id=1088， ， 的确是一个意思 |
| 9 bjrjk 2017 年 9 月 17 日 via Android @hqtc https://renjikai.com/luogu-p1434/ 送给楼主一个之前自己写过的化学的题解，c++版本的。 |
 | 10 victor97 2017 年 9 月 17 日 via Android 滑雪那道题可以看作是有向无环图，楼主的题意应该是无向有环图啊？这类图求最长路好像是 NP 问题。 |
 | 14 messyidea 2017 年 9 月 17 日 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 统计一下有流量的边就可以了 |
Select Language