We are given a n × n board with one square colored black, all others colored whi
ID: 3590468 • Letter: W
Question
We are given a n × n board with one square colored black, all others colored white. Your task is to cover the board with ”L” shaped tiles, such that all white squares are covered, the black square remains uncovered and there is no overlap among the L-shapes. An L-shape consists of three out of the 4 squares in a 2×2 square (thus one of the 2 × 2 = 4 squares is left uncovered by the shape). Design a divide-and-conquer algorithm to find a tiling of the board. Your algorithm will take as input the size n of one side(!) board and the position of the black square. You may assume that n 2 is a power of 2.
Explanation / Answer
n : is side (assuming power of 2)
p : is point(the location of black tile)
Point : we need to create a class with name Point which contain the x and y axis point location.
getTile( int n , Point p ) // Prototype of the method with the parameter.
1. Base Case :
when n=2 a 2 x 2 square with one cell missing it means it can be filled with a single tile.
Time Complexity:
If we form a Recurrence relation for above recursive algorithm can be written as below. Where C is a constant.
T(n) = 4T(n/2) + C
Time complexity : O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.