SquareTiling

Problem Statement

You are tiling a floor with square tiles. The floor is divided into unit squares, and each tile measures an integer multiple of the unit length on a side. Some or all of the unit squares of the floor may be obstructed. You wish to cover all unobstructed portions of the floor, but none of the obstructed portions, using as few tiles as possible. Tiles may not overlap and you may not cut the tiles.

The floor will be given as a String[], where each character represents one unit square ('.' indicates empty floor and '#' indicates an obstruction). Return the minimum number of square tiles necessary to cover the floor.

For example, the floor given by the input:

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

can be covered with a minimum of 5 square tiles, as shown in the figure below:

Definition

Class:

SquareTiling

Method:

squares

Parameters:

String[]

Returns:

int

Method signature:

int squares(String[] floor)

(be sure your method is public)

Constraints

• floor will contain between 1 and 12 elements, inclusive.
• Each element of floor will contain between 1 and 12 characters, inclusive.
• All elements of floor will have the same length.
• Each character in floor will be either '.' or '#".

Examples

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

   Returns: 1

   This floorplan can be tiled with a single 2x2 square tile.

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

   Returns: 4

   The optimal solution for this floorplan uses one 3x3 tile and three 1x1 tiles.

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

   Returns: 5

   This is the example from the problem statement.

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

   Returns: 1

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

   Returns: 23