Кубики могут быть сделаны из шести квадратов по бокам. Но вы также можете сложить три прямоугольника 2x1 пополам и склеить их вместе, чтобы сформировать куб. Теперь в этом задании вы получите набор кусочков, каждый из которых сделан из квадратов, и вы должны определить, можете ли вы выбрать кусочки, чтобы сформировать единичный куб. Не все части должны быть использованы, могут быть некоторые остались.

Детали

Части представлены в виде строки из двух разных символов или черно-белого изображения или любого удобного 2D-растрового формата. Далее я предполагаю, что пиксели, которые формируют части, являются черными, а фон - белым.

Два пикселя, которые имеют общую сторону, считаются принадлежащими одной и той же части. Куски могут быть сложены только вдоль линий сетки, которые разделяют пиксели, и их нельзя разрезать. Каждая сторона куба имеет размер в один пиксель, а каждая сторона куба может состоять только из одного слоя.

Вывод должен быть истинным или ложным значением.

Testcases

Далее пробелы являются фоновыми, а хеш-символы #представляют фрагменты.

(больше будет добавлено)

действительный

##  
 ## 
  ##

 #  
####
 #  

# # # # # # #

# ##
## #

Недействителен

###
###

#  #
####

### ## ####

Запустите следующий фрагмент для большего количества тестовых случаев.

document.getElementById("asdfasdf").style.display = "block";

<div id="asdfasdf" display="none">
<h3>Valid</h3>

    <pre><code>
    ##  
     ## 
      ##
    </code></pre>

    <hr>

    <pre><code>
     #  
    ####
     #  
    </code></pre>

    <hr>

    <pre><code>
    # # # # # # #
    </code></pre>

    <hr>

    <pre><code>
    # ##
    ## #
    </code></pre>

    <hr>

    <pre><code>
    #   #
    ###
      #
    </code></pre>

    <h3>Invalid</h3>

    <pre><code>
    ###
    ###
    </code></pre>

    <hr>

    <pre><code>
    #  #
    ####
    </code></pre>

    <hr>

    <pre><code>
    ### ## ####
    </code></pre>

    <hr>

    <pre><code>
    ##  ##  ##  ##  
    ##  ##  ##  ##  
      ##  ##  ##  ##
      ##  ##  ##  ##
    </code></pre>
  </div>

^{PS: это обобщение этой проблемы}

C 824 803 байта

#define Z return
#define Y char*b
#define N --n
i,j,n,w,h,A,B,C,D,E,F,G,H;char c[9999],*r,*d;x(b)Y;{if(b<c||*b<35)Z;++n;*b^=1;x(b-1);x(b+1);x(b-w);x(b+w);}m(b,p,y)Y,*p;{d=b;if(!y)for(y=-1,--p;1[++p]&31;)d+=w;for(i=0;*p&31?!(*p&16>>i)||b[i]&1:0;++i>4?p+=y,b+=w,i=0:0);Z!(*p&31)?x(d),n:0;}a(b)Y;{for(j=n=0;j<w*h;++j)if(m(c+j,b,1)||m(c+j,b,0))Z n;Z 0;}f(Y){bzero(c,9999);for(h=0,b=strcpy(c,b);r=b,b=strchr(b+1,10);h++,w=b-r);for(A=2,r=1+"@_`^C@|T@^R@XO@XX`|FB@|PP@|DD@PXN@XHX@XPX`PPXL@XHHX@XLDD@XPPX`PPPXH@PXHHH@PPPPP@";*r;r+=A+=r[-1]/96)while(a(r));A=B=C=D=E=F=G=H=0;while(a("PX")||a("XH")) (n-=3)?N?N?N?0:++H:++G:++F:++C;while(a("^")||a("PPPP"))(n-=4)?N?N?0:++H:++G:++E;while(a("P"))N?N?N?N?N?N?0:++H:++G:++F:++D:++B:++A;Z H||(G&&A)||(F&&B+B+A>1)||(E&&A>1)||D>1||C>1||((D||C)*3+B*2+A>5)*(A>1||B>2||A*B);}

Примечание: включает исправление ошибки (предыдущая запись ошибочно определила тромино и два домино как образующие куб). В коде драйвера TIO есть больше тестовых случаев, и теперь есть трекер прохождения / неудачи; Тестовые примеры hexomino были обновлены с использованием ожидаемого значения «пройдено / не пройдено» в метке.

Попробуйте онлайн!

... и прежде чем объяснять это подробно, стоит посмотреть на высоком уровне.

Базовый обзор

Этот алгоритм применяет средство сопоставления с образцом для классификации каждого найденного полиомино с заданным образцом в качестве своего подмножества. Когда полиомино сопоставляются, они «не отмечены», исключая их снова из сопоставления с образцом. Первоначальная классификация, задаваемая сопоставителем, представляет собой просто подсчет количества плиток в полиомино.

Соответствующий метод применяется первым, чтобы отбросить все полиомино, которые нельзя сложить на куб; классификация этих многочленов отбрасывается. Совпадение будет успешным, если эти полиомино появляются в пределах более высокого уровня; поэтому мы заботимся только о наименьшем подмножестве «не раскрываемых» для каждого класса. Здесь показаны наряду с дополненными кодировками все такие polyominoes (исключая их вертикальные отражения). Кодирование использует биты 4-0 каждого символа для представления квадратов в каждой строке:

[^C```] [XHX``] [PPPXH] [XHHX`] [PXN``] [|PP``]
 ####.   ##...   #....   ##...   #....   ###..
 ...##   .#...   #....   .#...   ##...   #....
 .....   ##...   #....   .#...   .###.   #....
 .....   .....   ##...   ##...   .....   .....
 .....   .....   .#...   .....   .....   .....
[|FB``] [XPX``] [PPXL`] [XLDD`] [XPPX`] [|DD``]
 ###..   ##...   #....   ##...   ##...   ###..
 ..##.   #....   #....   .##..   #....   ..#..
 ...#.   ##...   ##...   ..#..   #....   ..#..
 .....   .....   .##..   ..#..   ##...   .....
 .....   .....   .....   .....   .....   .....
[|T```] [^R```] [PXHHH] [XO```] [_````] [PPPPP]
 ###..   ####.   #....   ##...   #####   #....
 #.#..   #..#.   ##...   .####   .....   #....
 .....   .....   .#...   .....   .....   #....
 .....   .....   .#...   .....   .....   #....
 .....   .....   .#...   .....   .....   #....

[XX```]
 ##...
 ##...
 .....
 .....
 .....

После того, как эти полиомино отбракованы, мы классифицируем оставшиеся полиомино в соответствующие категории. Стоит отметить, что почти во всех случаях можно просто найти оставшиеся полиомино (складывающиеся в кубы) и просто искать суммы по шесть. Есть два исключения:

• Угол тромино и линия тромино не могут образовывать куб
• Линия тетромино и домино не могут образовывать куб

Чтобы соответствовать этому ограничению, мы формируем 8 категорий: AH для мономино (одиночные плитки), B для домино, C для угловых тромино, D для линейных тромино, E для линейных тетромино, F для других тетромино, G для пентомино и H для гексомино. Все, что не попадает ни в одну из этих категорий, просто игнорируется. Достаточно подсчета полиомино, которые попадают в каждую категорию.

В конце мы просто возвращаем правдивость или ложность, основываясь на гигантском уравнении и этих таблицах.

Разгромленный с комментариями

i,j,n,w,h,A,B,C,D,E,F,G,H;char c[9999],*r,*d;
x(b)char*b;{      // recursively unmarks polyomino pointed to by b.
   if(b<c||*b<35)return;
   ++n; *b^=1;    // Tabulates tiles in n as it goes.
   x(b-1);x(b+1);x(b-w);x(b+w); // left/up/down/right
}
m(b,p,y)char*b,*p;{ // pattern match area b with pattern p, direction y.
                    //   y=1 scans down; y=0 scans up.
   d=b; // d tracks a tile in the currently matched pattern for unmarking.
        // Note that all patterns are oriented to where "top-left" is a tile.
   if(!y) // ...when scanning up, move p to the end, set y to -1 to count backward,
          //    and advance d to guarantee it points to a tile (now "bottom-left")
      for(y=-1,--p;1[++p]&31;)d+=w;
   // Match the pattern
   for(i=0;*p&31?!(*p&16>>i)||b[i]&1:0;++i>4?p+=y,b+=w,i=0:0);
   return !(*p&31)   // If it matches...
          ? x(d),n   // ...unmark/count total polyomino tiles and return the count
          : 0;
}
a(b)char*b;{ // Scan for an occurrence of the pattern b.
   for(j=n=0;j<w*h;++j)
      if(m(c+j,b,1)||m(c+j,b,0)) // (short circuit) try down then up
         return n;
   return 0;
}
// This is our function.  The parameter is a string containing the entire area,
// delimited by new lines.  The algorithm assumes that this is a rectangular area.
// '#' is used for tiles; ' ' spaces.
f(char*b) {
   bzero(c,9999); // Init categories, c buffer
   for(h=0,b=strcpy(c,b);r=b,b=strchr(b+1,10);h++,w=b-r); // Find width/height
   // Unmark all polyominoes that contain unfoldable subsets.  This was
   // compacted since the last version as follows.  A tracks
   // the current pattern's length; r[-1], usually terminator for the
   // previous pattern, encodes whether the length increases; and o/c
   // the patterns were sorted by length.
   for(A=2,r=1+"@_`^C@|T@^R@XO@XX`|FB@|PP@|DD@PXN@XHX@XPX`PPXL@XHHX@XLDD@XPPX`PPPXH@PXHHH@PPPPP@";*r;r+=A+=r[-1]/96)
      while(a(r));
   A=B=C=D=E=F=G=H=0;
   // Match corner trominoes now to ensure they go into C.
   while(a("PX")||a("XH"))
      (n-=3)
         ?   --n
             ?   --n
                 ?   --n
                    ?   0 // More than 6 tiles?  Ignore it.
                    : ++H // 6 tiles?  It's an H.
                 : ++G // 5 tiles?  It's a G.
             : ++F // 4 tiles?  It's an F.
        : ++C; // only 3 tiles?  It's a C.
   // Now match line tetrominoes to ensure they go into E.
   while(a("^")||a("PPPP"))
      (n-=4)
         ?   --n
             ?   --n
                 ?   0 // More than 6 tiles?  Ignore it.
                 : ++H // 6 tiles?  It's an H.
             : ++G // 5 tiles?  It's a G.
         : ++E; // only 4 tiles?  It's an E.
   // Find all remaining tetrominoes ("P" is a monomino pattern)
   while(a("P"))
      --n
         ?   --n
             ?   --n
                 ?   --n
                     ?   --n
                         ?   --n
                             ?   0 // More than 6 tiles?  Ignore it.
                             : ++H // 6 tiles?  It's an H.
                         : ++G // 5 tiles? It's a G.
                     : ++F // 4 tiles?  It's an F.
                : ++D // 3 tiles?  It's a D.
            : ++B // 2 tiles?  It's a B.
         : ++A; // only 1 tile? It's an A.
   // Figure out if we can form a cube:
   return H               // Yes if we have a foldable hexomino
      ||(G&&A)            // Yes if we have a foldable pentomino
                          // and a monomino
      ||(F&&B+B+A>1)      // Yes if we have a foldable non-line tetromino
                          // and 2 other tiles (dominoes count twice).
                          // Either one domino or two monominoes will do.
      ||(E&&A>1)          // Yes if we have a foldable line tetromino (E)
                          // and two monominoes (A).  Note we can't make a
                          // cube with a line tetromino and a domino (B).
      ||D>1               // Yes if we have two line trominoes
      ||C>1               // Yes if we have two corner trominoes
      ||((D||C)*3+B*2+A>5)
                          // Any combination of trominoes, dominoes, monominoes>6,
                          // where trominoes are used at most once
                          // (via logical or)...
         * (A>1||B>2||A*B)
                          // ...times this includer/excluder fudge factor
                          // that culls out the one non-working case;
                          // see table:
                          //
                          // Trominos Dominos Monomos Cube  A>1 B>2 A*B
                          //    1        0       3+    yes   Y   N   0
                          //    1        1       1+    yes   Y   N   1
                          //    1        2       0     no    N   N   0
                          //    0+       3       0+    yes   Y   Y   1
      ;
}