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

一个算法询问各位大佬

  •  
  •   svt · 2021-05-20 14:13:52 +08:00 · 3426 次点击
    这是一个创建于 1281 天前的主题,其中的信息可能已经有所发展或是发生改变。

    要求如下: 一个 19x19 的地图,上面有的点放置了东西,有的点没有放。现在给了一个元件(一共有六个形状,随机给一个),需要判断这个元件能否放入到地图里。需要考虑元件旋转后的情况。

    下面我画了一个大概的图帮助理解:

    https://imgtu.com/i/goJsIJ

    https://imgtu.com/i/goYizq

    自己的大概思路是: 1.首先用广度优先遍历查出所有相连模块的最大面积

    2.按照面积顺序分组,大的在前,小的在后

    3.依次遍历最大面积,看是否能放下给定元件的各个形态。

    求各位大佬指点

    14 条回复    2021-05-28 10:29:32 +08:00
    aijam
        1
    aijam  
       2021-05-20 14:40:29 +08:00
    元件的长宽 x*y,搞个 x*y 的 sliding window 一一比对咯。
    dekuofa
        2
    dekuofa  
       2021-05-20 14:41:28 +08:00
    https://imgtu.com/i/godcJe 这种方式好像可行?
    jingniao
        3
    jingniao  
       2021-05-20 18:27:46 +08:00 via Android
    暴力遍历,选择元器件一点,放到所有点上,每个点 4 个方向,19 * 19 * 4
    newSimpleLife
        4
    newSimpleLife  
       2021-05-20 18:52:22 +08:00
    marl 一下, 挺好奇这种 dp 题目怎么写
    xupefei
        5
    xupefei  
       2021-05-20 19:42:29 +08:00 via iPhone
    只能遍历,所以最坏情况无论怎么遍历都是 19*19 。
    另外,这不是 dp 。
    misdake
        6
    misdake  
       2021-05-20 22:12:55 +08:00
    如果真的要追求运行速度的话,感觉还是暴力遍历比较快,做 2L 那样的用位运算优化。不用搞排序或者连接性。
    19x19 很小的,朝着缓存优化、分支优化的方向走,毕竟一个分支预测失败够算一行、一个 cache miss 的时间都够算一个元件了。
    循环里不申请内存,二维数组保证地址连续或者打成一维数组只用一层循环,判断能不能放的时候尽量减少分支。
    Xs0ul
        7
    Xs0ul  
       2021-05-20 22:55:59 +08:00 via Android
    楼主是不是看了个 puzzle 的视频
    lidlesseye11
        8
    lidlesseye11  
       2021-05-21 01:13:44 +08:00
    之前有看到过相似的帖子
    https://www.v2ex.com/t/708876
    虽然貌似也没有特别好的回复。。
    3dwelcome
        9
    3dwelcome  
       2021-05-21 01:51:18 +08:00
    微软有写过相关代码,但是很复杂。你可以在 google 搜"UVAtlas github"来找到。
    代码原目的是解决三维里的模型,在二维平面上投影展开的问题。行业里术语叫 UV 展开。

    就是类似楼主问题,二维贴图里,有一部分边和面是固定的。另外有一些剩余的零碎空间,怎么最大限度,塞入刚体变换后的小块元件。
    foxyier
        10
    foxyier  
       2021-05-21 11:55:29 +08:00
    这是要写俄罗斯方块脚本嘛。。
    yuanxing008
        11
    yuanxing008  
       2021-05-21 16:54:47 +08:00
    这不是塔科夫的仓库吗 哈哈哈
    TakaObsid
        12
    TakaObsid  
       2021-05-21 18:54:18 +08:00 via iPhone
    @Xs0ul gm 要火?
    Derpy2
        13
    Derpy2  
       2021-05-21 22:23:00 +08:00
    我想到一种 dp 的做法,不过看复杂度应该没什么意义
    对于只放一个元件,可以将这个元件按行切成块,然后 dp 数组为 dp[i][j][k],表示以 i,j 这个点为左下角,能放这个元件 1-k 行的内容,然后你就可以从 k 行推出 k+1 行能不能放。
    旋转的话只能当做不同的元件来看了。
    neruda
        14
    neruda  
       2021-05-28 10:29:32 +08:00
    其实这个问题比较简单。你们这样子想 19 * 19 = 361 把它转成一个一维的数组,同样的,6 个不同的图形也转换成相同坐标体系下的数组,如果你这个过程完成了,那么有点的是 1,没点的是 0,两个数组为位运算,如果是完全可以放下的,那么结果应该全部都是 0,那么问题的难点就是,元件的数据格式化,就是把它转换成一个 361 的数组。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5501 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 03:17 · PVG 11:17 · LAX 19:17 · JFK 22:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.