Solving the Island Problem: Finding the Largest Square Land
In the Island Problem, we are given a black and white bitmap representing an archipelago, where white denotes land and black denotes sea. The task is to determine the largest possible square land within the given bitmap. By analyzing the input array of boolean values representing land locations, we can identify the top-left coordinate and size of the largest square land. The solution involves identifying smaller squares within the map and iteratively determining the largest square. Through a step-by-step approach, the solution gradually explores and evaluates various possible square configurations to find the optimal one.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Island Problem Given a bitmap of aerial photographer of archipelago (chain of islands) Bitmap is black & white White means land Black means sea Find the largest possible square land
Island Problem Input 2D array of boolean called Land Size m x n Land[x][y] is true means location x,y is a land Output x,y the top-left coordinate of the largest square land and s, the size of the largest square land
Example x-axis (0,0) 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 Y-axis 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Example : Some of 2x2 square 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 2x2 2x2 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 2x2 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 2x2 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Solution : The largest square 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 4 x 4 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Example 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 3x3 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 3x3 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 3x3 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Sub-problem What should be our subproblem? Smaller maps? Divide maps by half? Smaller square?
Sub-problem What if we find all possible square? How the solution of n x n square constitute the solution of (n+1) x (n+1)?
Sub-problem 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 Land here 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 3x3 0 1 1 1 1 1 0 0 1 1 3 x 0 0 1 1 1 3x3 1 0 0 0 0 3 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
Sub-problem 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 Land here 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 2x2 1 0 1 1 1 1 1 1 0 0 1x1 1x1 0 0 0 1 0 0 0 0 0 0
Recursion b2[x][y] x,y (input Land[x][y], m, n) Biggest[x,y] = Min(Biggest[x+1,y+1], Biggest[x ,y+1], Biggest[x+1,y ]) + 1 if Land[x,y] 0 if not land[x,y]
Sub-problem 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 2 1 0 0 0 3 2 1 0 0 2 3 2 1 0 2 2 1 0 0 1 3 2 1 0 1 1 1 0 0 0 4 3 2 1 0 0 2 1 0 1 3 3 2 1 0 0 1 1 0 0 2 2 2 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0
