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:
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]