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
unitsquare 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 gridsquare 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 



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)  


1)  


2)  


3)  


4)  

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 (idx1)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);
}
No comments:
Post a Comment