要求如下: 一个 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 的数组。
|