Dynamic Programming with profile - example 3

This is a problem from TopCoder SRM 383 DIV1 - 500 point.

Here is a link to the problem statement : http://community.topcoder.com/stat?c=problem_statement&pm=8397&rd=10806

Here is the problem statement.

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 vector <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: vector <string> Returns: int Method signature: int layout(vector <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
0)
	{"....." ,"....." ,"....." ,"....." ,"....."} Returns: 5 5 boards laid side-by-side will cover this square room.
1)
	{"......." ,".#..##." ,".#....." ,".#####." ,".##..#." ,"....###"} 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.
2)
	{"####" ,"####" ,"####" ,"####"} Returns: 0 This is a strange room, with no floor area to cover.
3)
	{"...#.." ,"##...." ,"#.#..." ,".#...." ,"..#..." ,"..#..#"} Returns: 9 An optimal pattern here is: ---#|| ##--|| #-#||| |#-||| ||#||| ||#||#
4)
	{".#...." ,"..#..." ,".....#" ,"..##.." ,"......" ,".#..#."} Returns: 9

Approach
Let
R = number of rows in room.
C = number of columns in room.
Constraints tell us that 1 <= R,C <= 10

From small constraints, we can try the following approach :
Go through each row and try every possible combination.
Each row has at most 10 columns. So 2^10 maximum combination.
There are at most 10 rows.
So at worst, it will take 10 * 2^10 = 10 * 1024 = 10,240 operations.
Formally, runtime is O(R * 2^C)

Let's define state, recurrence, and profile.

State
dp[idx][profile]
= minimum number of boards we can use to cover all the areas from row[0] to row[idx] 
   when (idx-1)th row has configuration of profile.

Recurrence
The shape of each row depends on the shape of the previous row.

Profile
Binary representation of the previous row.
(i)th bit of profile is set if (i)th column of the row is a part of a vertical strip.
0 otherwise( which means it is either a pillar or a part of a horizontal strip).



Source code

class FloorBoards {

public:

int layout(vector <string>);

};

int R;

int C;

int mem[11][1<<10];

vector<string> room;

/*

 "mask" is a binary number representing shape of the previous row.

 (i)th bit of mask is set to 1 if (i)th column of the previous row is a part of a vertical strip.

 0 otherwise.

 */

int rec(int idx, int mask)

{

    if(idx == R) return 0;

    

    int& res = mem[idx][mask];

    if(res!=-1) return res;

    

    res = INF;

    

    for(int i=0; i < (1<<C); i++)

    {

        //check validity of the current config

        bool isValid = true;

        for(int j=0; j < C; j++)

        {

            if( ((i>>j) & 1) && ( room[idx][j] == '#') )

            {

                isValid = false;

                break;

            }

        }

        if(!isValid) continue;

        

        //Count the number of vertical and horizontal strips to use for the current row.

        int vert = 0;

        int hori = 0;

        bool isHori = false;

        for(int j=0; j < C; j++)

        {

            /*

             It is a vertical strip.

             If the current column of the above row is also a part of a vertical strip,

             the current square is a part of the continuation of the previous vertical strip.

             Only use a new vertical strip if the previous column is not a part of a vertical strip.

             */

            if( (i>>j) & 1)

            {

                isHori = false;

                if( ((mask>>j) & 1) == 0 )

                    vert++;

            }

            else // The current square is either a pillar or a horizontal strip

            {

                if(room[idx][j] == '#') //It is a pillar

                {

                    isHori = false;

                }

                else //It is a horizontal strip

                {

                    if(!isHori)

                    {

                        isHori = true;

                        hori++;

                    }

                }

            }

        }

        res = min(res, vert + hori + rec(idx + 1, i));

    }

    return res;

}

int FloorBoards::layout(vector <string> _room) {

    room = _room;

    R = room.size();

    C = room[0].size();

    memset(mem, -1, sizeof(mem));

    

return rec(0,0);

}