The brute force solution passes easily if implemented correctly. So, what do we need to do. First we loop over our array, if there is a '.' then we stop there and start the procedure. We need to form a square as big as possible. When we found a square (on the first step is only 1 '.') then we should try expanding the size by 1 and checking again whether the new square is full of only '.'s or not. For making our solution a little faster we can only check the new row and the column which we added to form a square of one size larger than the previous. For being more clear have a look at the pictures below.
The black cyrcles represent the are which we already found as a square and the red ones are the places where we need to check to see if we can expand our house by 1. As you can see there is only 1 row and 1 column to check, this makes the solution faster and it is important because in the task the maximum value of N is not stated. Check the source code for implementation.
No comments:
Post a Comment