Pretty simple challenge here. Who can make the fastest algorithm (lowest time complexity) to determine whether or not the circle is "boxed in" given the following setup?
Input: Your program receives a pair of numbers (a,b)
that denotes the position of a circle on a grid like this with arbitrary dimensions:
Where a-1
is the number of units from the right, and b-1
is the number of units from the bottom. Assume that (a,b)
is always a white square. The program should work for arbitrary arrangements of purple squares .
Definition of "boxed in": A circle at S=(a,b)
is "boxed in" if there is no path from S
consisting of vertical, horizontal, and diagonal one space moves that reaches a white square on the edge of the grid without going on a purple space. This means that:
is boxed in, but:
is not because of the open diagonal.
Output: A Boolean - is in boxed in, or not?
You can choose whatever data structure you want to represent the grid. Remember though, the goal is speed so keep that in mind.
[please note this is my first post on this SE site, so if I need to fix something let me know]
(a,b)
. I also just noticed you have two winning criterion tags code-challenge and fastest-algorithm. I assume you just want fastest-algorithm \$\endgroup\$ – Jo King Feb 8 at 12:31