Editorial for Wesley's Anger Contest 2 Problem 3 - Pumpkin Counting
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
There are multiple ways to efficiently count the pumpkins. We'll describe one of such methods below.
First, observe that a pumpkin is represented as a patch of black and white pixels. We can go through the grid and find all patches of connected pixels (two pixels are connected if they share at least one corner). One way to find all such patches is using a breadth first search and returning the coordinates of the patch.
For every one of the patches, we can generate a pumpkin with the same size as the patch. If the pixels match, then the patch is a valid pumpkin. Careful attention must be given to check if the size of the pumpkin is a positive integer.
Time Complexity:
Comments