一个算法询问各位大佬
这是一个创建于 1605 天前的主题，其中的信息可能已经有所发展或是发生改变。
要求如下： 一个 19x19 的地图，上面有的点放置了东西，有的点没有放。现在给了一个元件（一共有六个形状，随机给一个），需要判断这个元件能否放入到地图里。需要考虑元件旋转后的情况。
下面我画了一个大概的图帮助理解：
自己的大概思路是： 1.首先用广度优先遍历查出所有相连模块的最大面积
2.按照面积顺序分组，大的在前，小的在后
3.依次遍历最大面积，看是否能放下给定元件的各个形态。
求各位大佬指点
 | 1 aijam 2021-05-20 14:40:29 +08:00 元件的长宽 x*y，搞个 x*y 的 sliding window 一一比对咯。 |
 | 2 dekuofa 2021-05-20 14:41:28 +08:00 https://imgtu.com/i/godcJe 这种方式好像可行？ |
 | 3 jingniao 2021-05-20 18:27:46 +08:00 via Android 暴力遍历，选择元器件一点，放到所有点上，每个点 4 个方向，19 ＊ 19 ＊ 4 |
 | 4 newSimpleLife 2021-05-20 18:52:22 +08:00 marl 一下， 挺好奇这种 dp 题目怎么写 |
 | 5 xupefei 2021-05-20 19:42:29 +08:00 via iPhone 只能遍历，所以最坏情况无论怎么遍历都是 19*19 。 另外，这不是 dp 。 |
 | 6 misdake 2021-05-20 22:12:55 +08:00 如果真的要追求运行速度的话，感觉还是暴力遍历比较快，做 2L 那样的用位运算优化。不用搞排序或者连接性。 19x19 很小的，朝着缓存优化、分支优化的方向走，毕竟一个分支预测失败够算一行、一个 cache miss 的时间都够算一个元件了。 循环里不申请内存，二维数组保证地址连续或者打成一维数组只用一层循环，判断能不能放的时候尽量减少分支。 |
 | 7 Xs0ul 2021-05-20 22:55:59 +08:00 via Android 楼主是不是看了个 puzzle 的视频 |
 | 8 lidlesseye11 2021-05-21 01:13:44 +08:00 |
 | 9 3dwelcome 2021-05-21 01:51:18 +08:00 微软有写过相关代码，但是很复杂。你可以在 google 搜"UVAtlas github"来找到。 代码原目的是解决三维里的模型，在二维平面上投影展开的问题。行业里术语叫 UV 展开。 就是类似楼主问题，二维贴图里，有一部分边和面是固定的。另外有一些剩余的零碎空间，怎么最大限度，塞入刚体变换后的小块元件。 |
 | 10 foxyier 2021-05-21 11:55:29 +08:00 这是要写俄罗斯方块脚本嘛。。 |
 | 11 yuanxing008 2021-05-21 16:54:47 +08:00 这不是塔科夫的仓库吗 哈哈哈 |
 | 13 Derpy2 2021-05-21 22:23:00 +08:00 我想到一种 dp 的做法，不过看复杂度应该没什么意义 对于只放一个元件，可以将这个元件按行切成块，然后 dp 数组为 dp[i][j][k]，表示以 i,j 这个点为左下角，能放这个元件 1-k 行的内容，然后你就可以从 k 行推出 k+1 行能不能放。 旋转的话只能当做不同的元件来看了。 |
 | 14 neruda 2021-05-28 10:29:32 +08:00 其实这个问题比较简单。你们这样子想 19 * 19 = 361 把它转成一个一维的数组，同样的，6 个不同的图形也转换成相同坐标体系下的数组，如果你这个过程完成了，那么有点的是 1，没点的是 0，两个数组为位运算，如果是完全可以放下的，那么结果应该全部都是 0，那么问题的难点就是，元件的数据格式化，就是把它转换成一个 361 的数组。 |
Select Language