Statistics

Problem Statement for "FloorBoards"

Problem Statement

You are building a house and are laying the floorboards in one of the rooms. Each floorboard is a rectangle 1 unit wide and can be of any positive integer length. Floorboards must be laid with their sides parallel to one of the sides of the room and cannot overlap. In addition, the room may contain features such as pillars, which lead to areas of the floor where no floorboards can be laid. The room is rectangular and the features all lie on a unit-square grid within it. You want to know the minimum number of floorboards that you need to completely cover the floor.


You are given a String[] room containing the layout of the room. Character j in element i of room represents the grid-square at position (i, j) and will be a '.' if this square needs to be covered with a floorboard or a '#' if the square is a feature where no floorboard can be laid. Return an int containing the minimum number of floorboards you need to completely cover the floor.

Definition

Class:
FloorBoards
Method:
layout
Parameters:
String[]
Returns:
int
Method signature:
int layout(String[] room)
(be sure your method is public)

Constraints

  • room will contain between 1 and 10 elements, inclusive.
  • Each element of room will contain between 1 and 10 characters, inclusive.
  • Each element of room will contain the same number of characters.
  • Each character in room will be a '.' or a '#'.

Examples

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

    Returns: 5

    5 boards laid side-by-side will cover this square room.

  2. {"......." ,".#..##." ,".#....." ,".#####." ,".##..#." ,"....###"}

    Returns: 7

    A possible optimal layout could look like the following |------ |#--##| |#----| |#####| |##--#| |---### Each floorboard is represented by a consecutive horizontal sequence of '-' characters or a consecutive vertical sequence of '|' characters.

  3. {"####" ,"####" ,"####" ,"####"}

    Returns: 0

    This is a strange room, with no floor area to cover.

  4. {"#...#.",".##...","......","......","....##","##...."}

    Returns: 8

  5. {"#.#...",".#....",".#....","...#..","##.##.","......"}

    Returns: 8

  6. {"..#...","...#..","...#..","..#...",".###..","#.#..."}

    Returns: 9

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

    Returns: 9

    An optimal pattern here is: ---#|| ##--|| #-#||| |#-||| ||#||| ||#||#

  8. {".#...." ,"..#..." ,".....#" ,"..##.." ,"......" ,".#..#."}

    Returns: 9

  9. {"..........",".....#..#.","...#...#.#",".#....##.#","#.........","..##..#...","...###..#.","#..#.....#","#..##..#..","..##......"}

    Returns: 22

  10. {"......#..#","..###.....","......#.#.","#..#.#...#","..##..##..","#.........",".#.#.###..","..##.#.#..",".........#",".....#..##"}

    Returns: 23

  11. {"#.#.#.#...",".##.......","..#....#..",".##.......","....#.#...",".........#",".#.#.#..#.","..##..#..#","...#.#..#.",".......#.."}

    Returns: 24

  12. {".##...##..","......##..","....##....","....#.....","#.##....#.",".#..#.#...",".......#..","..#....#..","..#...#...",".......#.."}

    Returns: 21

  13. {"###...#..#","##.....#.#","#.....#.#.","....#..#..",".#.#......",".##....##.","...#......",".#..#.....",".#......#.","##....#..#"}

    Returns: 21

  14. {"..#.......",".#.....#..","...#..#...","#.##..#...","...##..#..",".##...#..#","#......#..",".#...#.#..","##...#....",".###.#..#."}

    Returns: 24

  15. {"#....#.#..","......###.",".#...#....","..##......",".#..#..#..","..#....###","........#.",".##...#...",".#......#.","..#....#.."}

    Returns: 23

  16. {"#..###.#..",".....#####",".#..#.....","#.##......","....#.....","#.........","..##......",".#.....#..","..##.###.#","......#..#"}

    Returns: 22

  17. {".#.....#..","##...#...#",".##....#..",".#.#......","#....#.##.",".##.#.....","..........",".#...#....","...##....#",".#......#."}

    Returns: 23

  18. {".###......","...#....#.",".#....#...",".#.#...###","#..###....","..##......","..#..#..##","..#.....#.",".....#....",".......#.."}

    Returns: 21

  19. {"###.#.###.","#.#####..#",".###..###.",".#.#...###",".#####.##.","...#..#.#.","#.##..###.","#.##.###..","#####.##.#","#...######"}

    Returns: 20

  20. {"###.###.#.","#...##.##.","..##..#.##",".###..####","...###.###","####.#.#.#","###..#.###","####..##.#","##.##.#.#.","####.###.#"}

    Returns: 22

  21. {"##.##.#...","#####.##.#","#..#.#####","#..#..#.#.","#.#.#..#.#","##.#.#.##.","#######..#","#####...##",".####.#.##","####.####."}

    Returns: 23

  22. {".#..#####.","##..#####.","..#####..#",".#####..#.","###.##.##.","#.#.#.##..","##.#######","##...#.#.#","#..#.#####","..#####..#"}

    Returns: 22

  23. {"#..####.##","#...##..#.","##.#..###.","#####.#.##","..#.#.####","##.#...##.","...##..###","##..#####.","..#.######","##..#####."}

    Returns: 21

  24. {".##.######","#..#####..","....####.#","####.###.#","#####...#.","##.##.#.#.","#.#.####.#","#....#.###","###.##..#.",".##.#.##.#"}

    Returns: 23

  25. {"#.#####.##","##########",".#...###..","####.#.##.","##.###...#","..###...##",".#..####.#","##...#.##.",".#.#######",".###..#.#."}

    Returns: 23

  26. {"...##..#..",".####...#.","######..##","##..######","##########","##.#.###..","##..#.#...",".#.#..###.","..##.#.###","###.####.#"}

    Returns: 21

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

    Returns: 23

  28. {"##.###.##.","######..##",".###..#.#.","##...###..","###..###.#","###..##.##","##.#.###..","##.####.##",".##.##...#","#.####.###"}

    Returns: 20

  29. {".......#..",".......#.#","....#.....","..........","....#.....","..........","........#.","..#.......","..#.#..#..",".........."}

    Returns: 15

  30. {".##.......","..........","......#...","..#.......","#......#..",".#........","..........","..........","....#.....","...#......"}

    Returns: 16

  31. {"....#.....",".....#....","..........","..........","..........",".#..#....#",".....#.#..",".......#..","..........","......#..."}

    Returns: 16

  32. {"...#...#..","..#.......","....#..#..","..........",".#........","..........",".......#..","..........","......##..",".......#.."}

    Returns: 16

  33. {".#........","..........",".........#",".......#..","..........","........#.","....##....","..........","#.#......#","....#....."}

    Returns: 16

  34. {"..........","#.........","#......#..","......#..#","..........","#.........",".......#..","..........","..........",".....##.#."}

    Returns: 15

  35. {".......#..",".........#","..........",".#.....#..","....#.....","..........","........#.",".........#","......#...",".......#.."}

    Returns: 17

  36. {"..##...#..","..........","..........","..........",".#........","#.....#...",".#........","..........",".#......#.","......#..."}

    Returns: 16

  37. {"..........","..#.......","..........","#......#..","...#...#..","...#......","#.........","....#.....","#.........",".....#...."}

    Returns: 17

  38. {"#.........","....#.....","...#......","..#.......","..........","..........",".....#..#.","..........","..........","...#....##"}

    Returns: 15

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

    Returns: 10

  40. {"##########" ,"######.###" ,"######.###" ,"#......###" ,"###.##.###" ,"###.##.###" ,"###......#" ,"###.######" ,"###.######" ,"##########"}

    Returns: 4

  41. {".##","###",".#.","...",".#.","#.#"}

    Returns: 5

  42. {".","#",".",".","#",".","#","."}

    Returns: 4

  43. {"#..#.#.#.#","#.##..##.#","....#..#.#","..##.#..#.","##.###....","#...#..#..","##..#.....",".......#.."}

    Returns: 19

  44. {".##.#.","..#..#","..##.#","###...",".....#"}

    Returns: 7

  45. {"...#","##.#"}

    Returns: 2

  46. {".#...#..","#...#...","##.#####","#.......","#...#.#."}

    Returns: 10

  47. {"#.......","#..##...","..#..###",".#...#..",".##..#.#"}

    Returns: 10

  48. {"#.#","...","#.#","...","#..","#..","#..","##.","#.#",".#."}

    Returns: 8

  49. {"......#..#","....#..#..","...#...##.","..#.#.###.","...#.#..##","##..#..#.#","....#.###.","###.....#.",".##.###..."}

    Returns: 24

  50. {"....","#.##","###.","..##","....","...#","##..",".#.."}

    Returns: 9

  51. {".#.#...#.#", "..#...#...", ".....#...#", "#.#.#.#.#.", ".#...#....", "#...#.#.#.", "...#...#.#", "#...#.#...", ".#.#.#.#.#", "..#...#..." }

    Returns: 33

  52. {"....#.....", "...#.....#", "..#.....#.", ".#.....#..", "#.....#...", ".....#...#", "...##...#.", "...#....#.", "..#....#..", "#....#...." }

    Returns: 24

  53. {"....#..##.", ".#..#..#..", "......#...", "..#.....#.", "..#..#....", "..#.....#.", "#...#.....", "#.....#...", "...###....", ".....#...#" }

    Returns: 20

  54. {"..#..#..#.", "#..#..#..#", ".#..#..#..", "..#.....#.", "#..#..#..#", ".#..#..#..", ".....#..#.", "#..#..#..#", ".#.....#..", "..#..#..#." }

    Returns: 34

  55. {".#..#..#..", "###.#.####", "##..#.....", "###.#.###.", "#...#..##.", "###.#.###.", "##..#...#.", "###.#.###.", "#......##.", "#########." }

    Returns: 14

  56. {"...##...#.", "##...##.#.", "#...##..#.", "..#.##.#..", ".#.#.#....", "#....####.", "##.##.....", "#.##..##..", "#.#...#...", ".........." }

    Returns: 23

  57. {"###.#", "....#", "#.#.#", "#....", "#.###" }

    Returns: 4

  58. {"...##..#..", "#..#..#..#", "#.#.....#.", "..#.#.#.##", "..........", ".##.#.##.#", ".#..#.#...", "....#.....", "...#...##.", "#...##...." }

    Returns: 25

  59. {".#.#..#..#", "..#..##.#.", "#.#..#.#..", "...#.#...#", ".#.....#..", "...###...#", "#.....#...", ".##.#.#.#.", ".....#....", "...#....#." }

    Returns: 27

  60. {".......", ".#..##.", ".#.....", ".#####.", ".##..#.", "....###" }

    Returns: 7

  61. {"##..##..##", "..##..##..", "##..##..##", "..##..##..", "##..##..##", "..##..##..", "##..##..##", "..##..##..", "##..##..##", "..##..##.." }

    Returns: 25

  62. {".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#." }

    Returns: 50

  63. {"#.#", "...", "#.#" }

    Returns: 3

  64. {"#.#.#.#..#", "#.#.#..#.#", "#.#.#.#.##", ".#.#..#.##", "..........", "#.#.#.##.#", "..#.#..###", "......#.#.", "##..#.#.#.", "...##.#..." }

    Returns: 22

  65. {"##..#.....", "....#.#...", "....###..#", "....##..#.", "....#.#...", "...###...#", "....##..#.", "..........", "#.#.#.#.#.", "...###...#" }

    Returns: 21

  66. {"#.#.#.#.#.", "..........", "#.#.#.#.#.", "..........", "#.#.#.#.#.", "..........", "#.#.#.#.#.", "..........", "#.#.#.#.#.", "....###..." }

    Returns: 27

  67. {"####", "##.#", "##.#", "...." }

    Returns: 2

  68. {".#.#.#.#.#", ".#.#.#.#.#", ".#.#.#.#.#", ".#.#.#.#.#", "..........", ".#.#.#.#.#", ".#.#.#.#.#", ".#.#.#.#.#", ".#.#.#.#.#", ".#.#.#.#.#" }

    Returns: 10

  69. {"......##.#", "####....#.", "##.#..#.##", "....#.###.", "##.....#..", ".#..#.####", ".....#..#.", "#..###..##", "....#.####", "#.#.#..#.#" }

    Returns: 25

  70. {"#.#####.#", "#.......#", "#.#.#.#.#", "....#....", "###.#.###", "....#....", "#.#.#.#.#", "#.......#", "#.#####.#" }

    Returns: 12

  71. {"..#..#....", ".#..#..#..", "#..#..#..#", "..#..#..#.", ".#..#..#..", "...#..#..#", "#.#..#..#.", ".#.....#..", "...#.#....", "..#.....#." }

    Returns: 33

  72. {".....", ".#.#.", ".....", ".#.#.", "....." }

    Returns: 7

  73. {"...#.....#", "....#.....", ".....#....", "...#..#...", "#...#.....", "....#..#..", ".#........", "...###....", "...#......", "...##...#." }

    Returns: 20

  74. {"...#.#....", "..#..##..#", "...#......", "........#.", "..##......", "..#.#.#...", ".#......#.", ".#..#.....", ".....#....", "...#.....#" }

    Returns: 22

  75. {"###.", "....", "###." }

    Returns: 2

  76. {"....#..#..", "##....#...", ".#.#.#.#.#", "..........", "#.#.#.#.#.", "###...##..", ".....####.", ".##.##....", "#....#...#", "...#.....#" }

    Returns: 24

  77. {"#...#....#", ".#....#..#", ".######..#", "..#.......", ".##..###..", "..#.#....#", "..#..#...#", ".##...#..#", ".#.....#..", "#........." }

    Returns: 20

  78. {".##..#..##", "#......###", "..........", "#......###", "#....#..##", ".......##.", "#....##...", "..#.#...##", "..........", "#........#" }

    Returns: 17

  79. {"#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#.#.#.#.", ".#.#.#.#.#" }

    Returns: 50

  80. {".#.#.#.#..", "#.#.#.#..." }

    Returns: 9

  81. {".#.#.#..##", ".#.#.#..##", "######..##", ".#.#......", ".#.#.#..##", "#####.....", "######....", "#####..#.#", "##.##.#..#" }

    Returns: 16

  82. {"......#...", ".#....#...", "..#...#...", ".........#", "#.....#...", "...#.#....", "....#.#...", ".........#", "#.....#...", "..#...#..." }

    Returns: 21

  83. {"###..###", "###..###", "###..###", "...#####", "#####...", "###.####", "###.####", "###.####" }

    Returns: 5

  84. {"#####.####", "#####.####", "#####.####", "#####.####", "..........", "#####.####", "#####.####", "#####.####", "#####.####", "#####.####" }

    Returns: 3

  85. {"..........", "..........", "..........", "..........", "..........", "....#...#.", "..........", "..........", "..........", ".........." }

    Returns: 12

  86. {".###.", ".#.#.", ".#.#.", ".#.#.", ".#.#.", "....." }

    Returns: 4

  87. {"###.###", "###.###", "###.###", ".......", "###.###", "###.###", "###.###" }

    Returns: 3

  88. {"####.##.##", ".###..####", "##....#.##", "###..##...", "....#.....", "#.#.#####.", ".#####.#.#", "###....#.#", "..##.####.", "##.#######" }

    Returns: 20

  89. {"..#..#..#.", "..#..#..#.", "...#...#..", "#.#.#.#.#.", ".#...#...#", ".##..#..#.", "..........", "#.#.#.#.#.", ".#.#.#.#.#", ".#.#.#.#.#" }

    Returns: 27

  90. {"...", "...", ".#." }

    Returns: 3

  91. {"#.#.#...#.", "...#.#.#..", "#.#...#.#.", ".#.#.#...#", "#...#.#.#.", ".#.#...#.#", "..#.#.#...", ".#...#.#.#", "#.#.#...#.", "...#.#.#.." }

    Returns: 38

  92. {"####.####", "####.####", "#.......#", "#.......#", "#.......#", "#.......#", "####.####", "####.####" }

    Returns: 6

  93. {"...#", "...#", "#..#", "#..#" }

    Returns: 3

  94. {"##.##", "##.##", ".....", ".....", "##.##", "##.##" }

    Returns: 4

  95. {".#.#.#", "#.#.##", "####..", "....#.", "#.#.##", "######", "......", "######", "....#.", "######" }

    Returns: 13

  96. {".#.#.#.##.", "..#.###...", "#...######", ".##....###", ".#.###...#", "#..#.#.##.", ".#####.###", "....#.#.#.", ".##....##.", "###..##..#" }

    Returns: 25

  97. {"..#..#..#.", ".#..#..#..", "#..#..#..#", "..#..#..#.", ".#..#..#..", "#..#..#..#", "..#..#..#.", ".#..#..#..", "#..#..#..#", "..#..#..#." }

    Returns: 37

  98. {".#......#.", "..#..##...", ".#.##....#", "....##..#.", "#....#..##", "..#..#.##.", "...#..##..", "..#...#..#", "#..#.#....", "....#..#.." }

    Returns: 26

  99. {".#.#.#.#.#", "#.#.#.#.#.", ".#.#...#.#", "#.#.#.#.#.", ".#.#.#.#.#", "#...#.#.#.", ".#.#.#...#", "#.#.#.#.#.", ".#.#.#.#.#", "#.#...#.#." }

    Returns: 46

  100. {"##..#.....", "#######.#.", "#..#..#..#", "#.#.#.###.", "##.##.###.", "#..######.", ".#........", ".#.#...##.", "##......#.", ".#.##...##" }

    Returns: 19

  101. {"..#.....#.", "...####...", "####....##", "##########", "....#.#.#.", "....####..", "...#.#....", "#...#...##", "..........", "#..#...###" }

    Returns: 20

  102. {".#.#", "#..#", "#.#.", "...#", "#.#.", ".##.", ".#.#" }

    Returns: 9

  103. {"#.#", "...", "#.#", "..." }

    Returns: 4

  104. {"#..#######", "....######", "#.########", "#.########", "#.########", "#.##.#.#.#", "###......#", "####.#.#.#", ".#.######.", ".........." }

    Returns: 13

  105. {"#.#", "#.#", "#.#", "#.#", "...", "#.#", "..." }

    Returns: 4

  106. {"####.#####", "####.#####", "####.#####", "####.#####", "..........", "####.#####", "####.#####", "####.#####", "####.#####", "####.#####" }

    Returns: 3

  107. {".#.#.#.#", "#.#.#.#.", ".#.#...#", "#.#.#.#.", ".#.#.#.#", "#.#.#.#.", ".#.#.#.#", "#.#.#.#.", ".#.#.#.#", "#.#.#.#." }

    Returns: 39

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: