矩阵最长的连续路径算法~

[hqtc]

题目：

在一个 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 示例

[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}]}

[bjrjk]

加个记忆化搜索就行了，或者动态规划也行，稍后我写个代码放上来吧，有题目链接吗？

[starvedcat]

“连续吃宝物才可以前进”是什么意思？

[hqtc]

@starvedcat 就是字面意思啊，每次前进必须吃到东西啊，不能走空地。

[helica]

这不是 poj 那道滑雪吗

[hqtc]

@bjrjk 题目链接没有，我把自己写的蠢萌递归算法附上了。。你可以给稍微指点下，给个伪代码或者思路就好，感谢您的时间

[hqtc]

@helica 是吗，我不知道耶。。有没有链接什么的

[hqtc]

@helica google 了一下找到了。。http://poj.org/problem?id=1088， ， 的确是一个意思

[hqtc]

@helica 想想还是不太一样。。。滑雪 4x4 连续同一个数字的话就不用动了。。这个问题得拿到最长的遍历值

[bjrjk]

@hqtc https://renjikai.com/luogu-p1434/ 送给楼主一个之前自己写过的化学的题解，c++版本的。

[victor97]

滑雪那道题可以看作是有向无环图，楼主的题意应该是无向有环图啊？这类图求最长路好像是 NP 问题。

[bjrjk]

@hqtc 总该有测试输入输出什么的吧……

[bjrjk]

@hqtc 如果是搞 OI/ACM 的话，应该只是输出最后的路径长度吧。

[hqtc]

@bjrjk 不是 ACM 是一个游戏对战比赛，公司搞的。。要给路径的。。。

[messyidea]

好像可以用网络流做
建一张图。添加 4 个点 S，s，T，t
S->s 流量为 1，费用为 0
t->T 流量为 1，费用为 0
s->所有有食物的格子，流量为 1,费用为 1
所有有食物的格子->t，流量为 1,费用为 0
所有有食物的格子->它能走到的有食物的格子，流量为 1,费用为 1

然后跑一下 S->T 最大费用最大流貌似就好了
路径的话 dfs 统计一下有流量的边就可以了

[skadi]

@messyidea 万物皆流👍😂

[victor97]

@messyidea 流量都是 1，意义在哪里？正环怎么处理？

[messyidea]

@victor97 想太简单了，确实不能处理环。

还需要把每个有食物的格子拆成两点 ai 和 bi
ai -> bi 流量为 1, 费用为 1
bi->能到的其它节点的 aj， 流量为 1,费用为 0
s->ai, 流量为 1, 费用为 0
S->s, 流量为 1,费用为 0
bi->t,流量为 1,费用为 0
t->T,流量为 1,费用为 0

很久没搞这个了，不知道现在有没有漏洞了