CODEWITHSUNDEEP
algorithmdynamic-programmingbreadth-first-search
abhishhh1
abhishhh1

Reputation: 54

Fill the matrix with 2x1 tiles and minimize left spaces

I have given a matrix of size 5xN in which few cells are blocked ,I need to fill the matrix using tiles of size 1x2 such that left empty cells are minimum possible. We can place 1x2 tiles horizontally or vertically. If I place tiles vertically at cell(i,j) then I have to print 1 (i,j) otherwise print 2 (i,j). see the example below:

......
..#..#
##.#..             # -> blocked cells
##.##.             . -> empty cells
.####.

Solution for above matrix is:

2 (0,0) 
2 (0,2)
2 (0,4)
2 (1,0)
2 (1,3)
1 (2,2)
2 (2,4)
1 (3,5)

Final matrix:

######
######         (only one cell left empty)
######             
######             
.#####

I tried to solve using BFS but it is giving me time limit exceed, What other approach I can use to solve this problem optimally.

1<= N <=100

Upvotes: 1

Views: 651

Answers (1)

Tassle
Tassle

Reputation: 553

You can solve this in O(N) time and space using a mix of brute-force and dynamic programming.

To explain this, I'm going to represent a rule imposed on a column of 5 cells as a binary number b (for example 10011) where a "1" means that I place the left part of a horizontal tile on that cell, and "0" means I don't.

Now, you can define a DP table of size (N+1)*32 as follows:

  • DP[i][b] is the minimum possible number of empty cells in the first i columns if the column number i obeys the rule represented by b. If it is not possible to obey rule b on this column (because of the obstructions in your input matrix, or because we are at the last column of our matrix and thus cannot place a horizontal tile), then DP[i][b] = infinity.

As a base case you have DP[0][0] = 0 and DP[0][b] = infinity as I can not place any tile using 0 columns.

Then to compute DP[i][b] for i>0, for each rule b' on column i-1 that is compatible with rule b on column i you compute the following :

  • DP[i-1][b'] + the number of empty cells on column i if you obey the rules b and b' then put as many vertical tiles as possible on column i.

And set DP[i][b] to be the minimum among all such computed numbers. (Of course if rule b on column i is incompatible with the obstructions in your input matrix, then just set DP[i][b] to be infinity).

Once you have computed all these values (in increasing order of i), your answer will be DP[n][0] (as you can not put any horizontal tiles on the last column).

Upvotes: 1

Related Questions