数学吧 关注:841,017贴子:8,570,176

经典铺地毯问题

只看楼主收藏回复

各位大佬如何应对


IP属地:浙江来自Android客户端1楼2024-04-27 22:15回复
    分治吧


    IP属地:湖南来自Android客户端2楼2024-04-27 22:37
    回复
      1.根据样例容易得到灰色格子在主对角线上任意一个位置的构造。
      2.注意到灰色格子在一个特定的面积为4的正方形内移动都是合法的构造。
      这样就解决了灰色格子在主对角线上面一个格子和下面一个格子的情况。
      3.所以只要考虑剩下的位置就好了。比如3-1,4-1,4-2。
      在这三个位置的构造我们只需要在左上角4x4的正方形里考虑,然后再注意4-1其实在次主对角线上,结合1,2可以轻松解决这三个位置。
      4.其余三个正方形和3的情形没有本质区别。
      于是我们在8x8上解决了这个问题。
      对于nxn上的问题,恐怕没那么简单。


      IP属地:陕西来自Android客户端3楼2024-04-27 23:26
      收起回复
        由于任何一个L型图案x都可以用4种图案各一个来构成和x相似且相似比为2的大L图案,因此对于任意一个边长2^k的正方形,我们总是可以覆盖掉其中的3/4,然后剩下一个某个角上的小正方形,接下来就是递归的思路,我们又回到了原先的问题,但是问题规模变小了


        IP属地:北京来自Android客户端4楼2024-04-27 23:48
        回复
          码一下,明天醒了写个程序跑一下。这不就是经典的精确密铺问题么?写个X算法慢慢跑就完事了。


          IP属地:北京来自Android客户端6楼2024-04-28 02:02
          收起回复
            显然旋转单块可将空格移到任意位置


            IP属地:北京来自iPhone客户端7楼2024-04-28 02:48
            收起回复
              在4-3跟3-3不都在一个22的区域里?换一块毯子不就行了?


              IP属地:北京来自Android客户端8楼2024-04-28 09:21
              回复
                喜欢我谜题:问号吗


                IP属地:广东来自Android客户端9楼2024-04-28 09:35
                收起回复
                  找个俄罗斯方块高手来做


                  IP属地:黑龙江来自Android客户端10楼2024-04-28 09:51
                  回复
                    这样子转一下?


                    IP属地:天津来自Android客户端11楼2024-04-28 10:01
                    收起回复
                      如果没规定每种朝向的方块的使用数量不是有手就会?


                      IP属地:河北来自Android客户端12楼2024-04-28 10:08
                      回复
                        经典


                        IP属地:江苏来自Android客户端13楼2024-04-28 10:22
                        回复
                          中间小正方形转一下


                          IP属地:江西来自Android客户端14楼2024-04-28 10:35
                          回复
                            分治法例题


                            IP属地:辽宁来自Android客户端15楼2024-04-28 10:45
                            回复
                              那块红毯子顺时针转一下


                              IP属地:浙江来自Android客户端16楼2024-04-28 11:04
                              回复