Statistics

Problem Statement for "CubePainting"

Problem Statement

You are given a 3x3x3 cube. Each face of the cube contains a 3x3 grid of nine squares. Some of the squares are painted and the rest are unpainted. Your task is to calculate the number of ways you can cover all the unpainted squares with "cube-cycles".

A cube-cycle is a sequence of 3 or more squares, where each square is "cube-adjacent" to the next square, and the last square is "cube-adjacent" to the first square. All squares in a cube-cycle must be distinct. Two squares are cube-adjacent if they share a common edge. That common edge can be on a face or on an edge of the cube. Each square in the cube has exactly four cube-adjacent squares.

Note that two cube-cycles might be distinct even if they contain the same set of squares. See example 0.

You are given the cube as a String[] containing 54 characters, where each character represents a single square. The String[] will be formatted as a net of the cube, as shown below:

+---+
|   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |
+---+

Painted squares are represented by '*' characters and unpainted squares are represented by '.' characters. You are only allowed to cover unpainted squares with cube-cycles. You are not allowed to cover painted squares. All unpainted squares must be covered, and no two cube-cycles can overlap each other. Return the number of ways you can cover the cube modulo 1,000,000,007.

Definition

Class:
CubePainting
Method:
count
Parameters:
String[]
Returns:
int
Method signature:
int count(String[] cube)
(be sure your method is public)

Constraints

  • cube will contain exactly 9 elements.
  • Elements 0, 1, 2, 6, 7 and 8 of cube will each contain exactly 3 characters.
  • Elements 3, 4 and 5 of cube will each contain exactly 12 characters.
  • All characters in cube will be either '*' or '.'.

Examples

  1. {"***", "***", "***", "**....******", "**....******", "**....******", "***", "***", "***"}

    Returns: 3

    There are two ways to cover it with one cycle and one way with two cycles.    

  2. {"***", "***", "***", "************", "............", "************", "***", "***", "***"}

    Returns: 1

    There is only one way to cover a strip.

  3. {".*.", "***", ".*.", ".*..*..*..*.", "************", ".*..*..*..*.", ".*.", "***", ".*."}

    Returns: 1

    All squares in the corners should be covered. There are eight independent cycles.

  4. {"***", "***", "***", "************", "************", "************", "***", "***", "***"}

    Returns: 1

    All squares are painted in this case.

  5. {"*.*", "...", "*.*", "*.**.**.**.*", "............", "*.**.**.**.*", "*.*", "...", "*.*"}

    Returns: 0

  6. {"***", "***", "***", "............", "............", "............", "***", "***", "***"}

    Returns: 40661

  7. {"...","...","...","............","............","............","...","...","..."}

    Returns: 87358528

  8. {"*..","...","...","............","............","............","...","...","..."}

    Returns: 409157492

  9. {".*.","...","...","............","............","............","...","...","..."}

    Returns: 87043541

  10. {"...",".*.","...","............","............","............","...","...","..."}

    Returns: 147532253

  11. {".*.",".*.",".*.",".*..........",".*..........","............","...","...","..."}

    Returns: 20012102

  12. {"..*","...","..*","............","............","............","...","...","..."}

    Returns: 111610853

  13. {"..*","...","*..","............","............","............","...","...","..."}

    Returns: 171725628

  14. {"...","...","...","............",".*.....*....","............","...","...","..."}

    Returns: 159705949

  15. {"...","...","...","*...........",".*..........","..*.........","...","...","..."}

    Returns: 4109056

  16. {"...","...","...","...***......","...***......","...***......","...","...","..."}

    Returns: 13013856

  17. {"...","...",".*.","............","........*...","............","...",".*.","..."}

    Returns: 20036259

  18. {"...","...","...",".*.*..**.*..",".*.*..*.**..","**.*..*..*..","...","...","..."}

    Returns: 0

  19. {"...","...","...","*........***","*..........*","***........*","...","...","..."}

    Returns: 484645

  20. {"...",".*.","**.",".....**.....",".......*.*..","...*..*.**..","...","*..",".**"}

    Returns: 0

  21. {"*..","..*","...","..*.........","...*.*......","....*.*.....","...","...","..."}

    Returns: 0

  22. {"...","...","...","........*...","............","*...........","...","...",".*."}

    Returns: 19749086

  23. {"...","...","...",".*......*...","..........*.","............","...","...","..."}

    Returns: 31898771

  24. {".*.","..*","**.",".*.******...","....*..*....","....*.*.....","...","..*","..."}

    Returns: 0

  25. {"...","...","...","...*........",".*.**.....*.","............","...","...","..."}

    Returns: 614878

  26. {"*..","...","..*",".*.**....*.*","...*.......*","......**....","...","*.*","..."}

    Returns: 0

  27. {"...","...","...","............","............","............","...","...","..."}

    Returns: 87358528

  28. {"...","..*","...",".*....**..*.","........*...","...........*","...","...","..."}

    Returns: 75416

  29. {"...","..*","...","...**.......",".........*..","....*..**..*","**.","..*",".*."}

    Returns: 0

  30. {"...","...",".**","*..**.*...*.","*.......*...","...*.*......","...","*..","..*"}

    Returns: 18

  31. {"...","...","...",".......*..*.","............","............","...","...","..."}

    Returns: 132653669

  32. {"...","...","...","............","............","............",".*.",".*.","..*"}

    Returns: 36343737

  33. {"...","...","...","...***..*.*.",".*...*..*.*.",".....*......","...","...","..."}

    Returns: 35014

  34. {"...","...","...",".....**.....",".........*..",".........*..","...","...",".*."}

    Returns: 364374

  35. {"..*","***","*..","**.....*...*","....*...*...","............","...","...","..."}

    Returns: 0

  36. {"...","...",".*.","..*.........",".*....*.*.*.","**..*....*..","...","...","..."}

    Returns: 0

  37. {"...","...","...",".......*....","...........*","......*....*","...","..*",".*."}

    Returns: 0

  38. {"*..",".**","...","*.*..*...*..","....*......*","..****...*..","...",".*.","..."}

    Returns: 0

  39. {"...","...","...","...*..**....","..**........","..*...*.....","...","...","..."}

    Returns: 144126

  40. {"*..",".*.",".*.","...*..*.....","......*.*...","...*........","**.","..*",".*."}

    Returns: 0

  41. {"...","...","...","............","............","............","...",".*.","..."}

    Returns: 147532253

  42. {".*.","..*","...","..*......**.",".......*....",".*..**.*....","..*","*.*","..."}

    Returns: 3

  43. {"...","..*","*..","*..*.*..*.*.","......*.....","...***....**",".*.",".*.","*.."}

    Returns: 0

  44. {"*..","*..",".*.",".........*..","*...*.......","...*.....*.*","...","...","*.."}

    Returns: 0

  45. {"...","*..","**.","..*..*.*...*",".**..**.....","*.*.**..*.**","..*","*..","..*"}

    Returns: 0

  46. {"...","*.*","...","....*....*..","**.......*..","...*.....*..",".**","...",".**"}

    Returns: 0

  47. {"...","...","**.","..*...*.....",".**.****....","***..**..*.*","...",".**","..."}

    Returns: 0

  48. {"...","...","...",".......*....","*..*..*...*.",".......**.*.","...","...","..."}

    Returns: 0

  49. {"...","..*","...","............",".*......*...","............",".*.","...","..."}

    Returns: 1132211

  50. {".*.","...",".**","..**...*...*","...*...*.*..",".***.***....","**.",".*.",".*."}

    Returns: 0

  51. {"...",".*.","*..","........*...","....*.......",".*..*......*","...","...","..*"}

    Returns: 634

  52. {"**.","...","..*","*.*.*....**.","....*..**...","..*..*.***..","...","*..","..."}

    Returns: 0

  53. {"...","...","...",".*.........*","...........*","...*...**.*.",".*.","...","..."}

    Returns: 10983

  54. {"...","*.*",".**",".......**.*.","..*...*.....",".*.....*....","*..","*..","*.."}

    Returns: 0

  55. {"...","...","...","............","*...........","*...*.......","...","...","..."}

    Returns: 87808156

  56. {"..*","...",".*.","*.**.*....*.","*...*....*..","..*..*.*..**","...","*..",".*."}

    Returns: 0

  57. {"..*","**.",".*.","..**.*..*.*.","....**.*..**",".....*.*..*.","*.*",".**",".*."}

    Returns: 0

  58. {"...","...","...","............",".....*.*..*.",".....*.....*","*..","...","..."}

    Returns: 55634

  59. {".*.","*..","...","*...**..*..*","....*..***..","...*.....*..","...","*..","..."}

    Returns: 0

  60. {"***","***","***","************","************","************","***",".**","***"}

    Returns: 0

  61. {"***","***","***",".***********","************","*******.****","***","***","***"}

    Returns: 0

  62. {".*.","***","**.","*..*.*..**.*","*..*.***.**.","******..****","**.","***","***"}

    Returns: 0

  63. {"***",".**","**.","*****.**.***",".**.***.****","..*******.**","..*","***","*.."}

    Returns: 0

  64. {"***","***","***","****.*******","****.*******","************","***","***",".*."}

    Returns: 0

  65. {"..*","**.","***","************","**..********","****.**.***.","*.*","*..","..*"}

    Returns: 0

  66. {"***","***","***","*****.******","************","******.*****","***",".**","***"}

    Returns: 0

  67. {"***","***","***","************",".**.****.***","*******.****","***","***","***"}

    Returns: 0

  68. {"***",".**","***","************","********.***","************","***","***",".**"}

    Returns: 0

  69. {"***","***",".**","*********.**",".***********","************",".*.",".**",".**"}

    Returns: 0

  70. {"...",".*.","...","............",".*..*..*..*.","............","...",".*.","..."}

    Returns: 876011

  71. {"***",".*.","...","............",".*.**..*..*.","............","...",".*.",".**"}

    Returns: 27

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: