这是一个创建于 1287 天前的主题，其中的信息可能已经有所发展或是发生改变。
要求如下： 一个 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