V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hqtc
V2EX  ›  算法

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

  •  
  •   hqtc · 2017-09-17 15:28:51 +08:00 · 3963 次点击
    这是一个创建于 2625 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    在一个 10x10 矩阵中的某些格子上分布着宝物,某人从一处像贪吃蛇一样开始吃,但不会像贪吃蛇一样长身体,而且必须连续吃宝物才可以前进。前进方向 8 个相邻格子都可以,怎样的算法可以选择一条吃掉最多宝物的路线?

    我现在用递归做,但是碰到那种 4x4 以上连续宝物的地图就会超时。。。

    求高手解答~

    __

    感觉并不像贪吃蛇的问题,而是找一条最长的连续路径。。。

    第 1 条附言  ·  2017-09-17 16:25:48 +08:00
       // 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-09-17 17:16:57 +08:00

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

    17 条回复    2017-09-17 19:19:13 +08:00
    bjrjk
        1
    bjrjk  
       2017-09-17 16:02:50 +08:00 via Android   ❤️ 1
    加个记忆化搜索就行了,或者动态规划也行,稍后我写个代码放上来吧,有题目链接吗?
    starvedcat
        2
    starvedcat  
       2017-09-17 16:04:52 +08:00
    “连续吃宝物才可以前进”是什么意思?
    hqtc
        3
    hqtc  
    OP
       2017-09-17 16:16:01 +08:00
    @starvedcat 就是字面意思啊,每次前进必须吃到东西啊,不能走空地。
    helica
        4
    helica  
       2017-09-17 16:17:36 +08:00 via iPhone
    这不是 poj 那道滑雪吗
    hqtc
        5
    hqtc  
    OP
       2017-09-17 16:27:41 +08:00
    @bjrjk 题目链接没有,我把自己写的蠢萌递归算法附上了。。你可以给稍微指点下,给个伪代码或者思路就好,感谢您的时间
    hqtc
        6
    hqtc  
    OP
       2017-09-17 16:28:05 +08:00
    @helica 是吗,我不知道耶。。有没有链接什么的
    hqtc
        7
    hqtc  
    OP
       2017-09-17 16:31:34 +08:00
    @helica google 了一下找到了。。http://poj.org/problem?id=1088, , 的确是一个意思
    hqtc
        8
    hqtc  
    OP
       2017-09-17 16:37:24 +08:00
    @helica 想想还是不太一样。。。滑雪 4x4 连续同一个数字的话就不用动了。。这个问题得拿到最长的遍历值
    bjrjk
        9
    bjrjk  
       2017-09-17 16:38:19 +08:00 via Android
    @hqtc https://renjikai.com/luogu-p1434/ 送给楼主一个之前自己写过的化学的题解,c++版本的。
    victor97
        10
    victor97  
       2017-09-17 16:42:17 +08:00 via Android
    滑雪那道题可以看作是有向无环图,楼主的题意应该是无向有环图啊?这类图求最长路好像是 NP 问题。
    bjrjk
        11
    bjrjk  
       2017-09-17 16:47:36 +08:00
    @hqtc 总该有测试输入输出什么的吧……
    bjrjk
        12
    bjrjk  
       2017-09-17 16:52:55 +08:00
    @hqtc 如果是搞 OI/ACM 的话,应该只是输出最后的路径长度吧。
    hqtc
        13
    hqtc  
    OP
       2017-09-17 17:06:46 +08:00
    @bjrjk 不是 ACM 是一个游戏对战比赛,公司搞的。。要给路径的。。。
    messyidea
        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 统计一下有流量的边就可以了
    skadi
        15
    skadi  
       2017-09-17 18:37:42 +08:00 via Android
    @messyidea 万物皆流👍😂
    victor97
        16
    victor97  
       2017-09-17 18:54:37 +08:00 via Android
    @messyidea 流量都是 1,意义在哪里?正环怎么处理?
    messyidea
        17
    messyidea  
       2017-09-17 19:19:13 +08:00
    @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

    很久没搞这个了,不知道现在有没有漏洞了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4753 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 05:36 · PVG 13:36 · LAX 21:36 · JFK 00:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.