Suppose we have a field with coordinates, and the robot start from (0, 0), and can move up, down, left or right, but not diagonally.
For any given position (x, y), the robot can move to (x-1, y), (x+1, y), (x, y-1), (x, y+1), but not (x-1, y-1), (x+1, y+1), (x-1, y+1), (x+1, y-1).
In addition, there are obstacles placed in a way that any location whose coordinates' digits add up to 21 or more, e.g. (45, -94) is an obstacle point because 4 + 5 + 9 + 4 = 22 >= 21, but (-112, 223) is not because 1 + 1 + 2 + 2 + 2 + 3 = 11 < 21.
The robot cannot step into an obstacle or through it. It must move around it.
To determine the number of locations the robot can make, the first thought would be an exhaustive search with a breadth-first search.
- Is it the only way?
- Is there a faster way to do it?
- How can the knowledge of where obstacles are be used to solve it?
A point is an obstacle if either x or y = +/- 399, so there is a complete rectangle of obstacle points from (-399,-399) to (399,399).
Since you can't reach anything outside that rectangle, there are fewer than 640000 reachable points, and a simple BFS is probably a reasonable solution.