一个算法询问各位大佬

[svt]

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

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

https://imgtu.com/i/goJsIJ

https://imgtu.com/i/goYizq

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

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

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

求各位大佬指点

[aijam]

元件的长宽 x*y，搞个 x*y 的 sliding window 一一比对咯。

[dekuofa]

https://imgtu.com/i/godcJe 这种方式好像可行？

[jingniao]

暴力遍历，选择元器件一点，放到所有点上，每个点 4 个方向，19 ＊ 19 ＊ 4

[newSimpleLife]

marl 一下， 挺好奇这种 dp 题目怎么写

[xupefei]

只能遍历，所以最坏情况无论怎么遍历都是 19*19 。
另外，这不是 dp 。

[misdake]

如果真的要追求运行速度的话，感觉还是暴力遍历比较快，做 2L 那样的用位运算优化。不用搞排序或者连接性。
19x19 很小的，朝着缓存优化、分支优化的方向走，毕竟一个分支预测失败够算一行、一个 cache miss 的时间都够算一个元件了。
循环里不申请内存，二维数组保证地址连续或者打成一维数组只用一层循环，判断能不能放的时候尽量减少分支。

[Xs0ul]

楼主是不是看了个 puzzle 的视频

[lidlesseye11]

之前有看到过相似的帖子
https://www.v2ex.com/t/708876
虽然貌似也没有特别好的回复。。

[3dwelcome]

微软有写过相关代码，但是很复杂。你可以在 google 搜"UVAtlas github"来找到。
代码原目的是解决三维里的模型，在二维平面上投影展开的问题。行业里术语叫 UV 展开。

就是类似楼主问题，二维贴图里，有一部分边和面是固定的。另外有一些剩余的零碎空间，怎么最大限度，塞入刚体变换后的小块元件。

[foxyier]

这是要写俄罗斯方块脚本嘛。。

[yuanxing008]

这不是塔科夫的仓库吗 哈哈哈

[TakaObsid]

@Xs0ul gm 要火？

[Derpy2]

我想到一种 dp 的做法，不过看复杂度应该没什么意义
对于只放一个元件，可以将这个元件按行切成块，然后 dp 数组为 dp[i][j][k]，表示以 i,j 这个点为左下角，能放这个元件 1-k 行的内容，然后你就可以从 k 行推出 k+1 行能不能放。
旋转的话只能当做不同的元件来看了。

[neruda]

其实这个问题比较简单。你们这样子想 19 * 19 = 361 把它转成一个一维的数组，同样的，6 个不同的图形也转换成相同坐标体系下的数组，如果你这个过程完成了，那么有点的是 1，没点的是 0，两个数组为位运算，如果是完全可以放下的，那么结果应该全部都是 0，那么问题的难点就是，元件的数据格式化，就是把它转换成一个 361 的数组。