Reputation: 54
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
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:
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 :
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