Given a N*M grid containing some obstacles represented by ‘#’ and remaining empty cells represented by ‘.’, Determine if it is possible to color only the empty cells if we can color a 2*2 sub-rectangle in one move if it doesn’t contain any obstacles. Note that we don’t need to count the number of moves, just tell whether it is possible to color or not.
SUPER QUICK EXPLANATION
- Just find all the positions where we can make a move, and store the result of moves in another array.
- If there’s an empty cell in the grid, which cannot be colored by any operation, It is impossible to color that cell, hence the answer is impossible.
Let’s define a position (i,j) valid, if all four positions (i,j),(i,j+1),(i+1,j) and (i+1,j+1) are empty positions, because we can apply the move here without coloring any obstacles.
First of all, we find all the valid positions in the grid and store the result of applying move at that position.
For this purpose, we can make an auxiliary grid, where we mark the positions which can be colored using operations at any valid position.
Now, We know where the moves can be applied, so make another grid, and find out the final grid after applying all operations.
Now, If all the empty cells from given grid are marked colored, then it is possible to color all empty cells without coloring any obstacles, so print Yes. Otherwise, print No.
Also, Prefix/Suffix sums combined with grid or even 3-dimensional arrays form interesting problems, and thus, are a nice topic for practice.
Another Interesting grid problem involves dynamic-programming on grids depending upon some conditions, which you may find here.
Time complexity is O(N*M) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.