How to Find the Maximum Accessible Area on a 2D Grid

I came across this question on StackOverflow listed under Dynamic Programming, but there didn’t seem to be an accepted solution with an explanation — so I figured I’d give it a shot and document the solution along-with my thought process.

Enjoy!

The Problem

There is a character who can move around on a two-dimensional (x,y) coordinate grid. The character is placed at point (0,0).

From (x, y) the character can move to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).

Some points are dangerous and contain land mines. To know which points are safe, we check whether the sum of the digits of abs(x) plus the sum of the digits of abs(y) are less than or equal to 23.

For example, the point (64, -59) is not safe because 6 + 4 + 5 + 9 = 24, which is greater than 23. The point (105, -17) is safe because 1 + 0 + 5 + 1 + 7 = 14, which is less than 23.

How large is the area that the character can access?

The Solution

Before we code this solution, it’s important to understand the coordinate system of a graph in the real world vs its programmatic representation.

The Coordinate System

To start off you first need to remember that an

Array

cannot have negative indices, therefore in order to create a graph that has both negative and positive coordinates you need to have an array twice as long as the

0..n

length of an axis. For example, if you need the x-axis to range from

-100..100

you will need an array of length

AXIS_LENGTH * 2

to accommodate these coordinates where

AXIS_LENGTH = 100

.

Since a graph is technically a data structure represented using rows and columns, we can easily represent it using a 2D array.

When representing a graph using a 2D array the y-axis will become inverted (i.e. the positives of the values of the y-axis will be below the origin point) because in the real-world the y-axis is represented bottom-up whereas in an array we cannot maintain inverted indices.

We consider the origin point of a real-world graph to be at (0, 0) — however, if we attempt to use these same coordinates to map the origin point in our 2D array, you’ll see that

graph[0][0]

will point to the upper-left most coordinate at (-5, -5), and not the coordinate at the centre of the grid. The actual origin of the graph in the real-world as well as for our solution should be the coordinate at the centre of the grid.

In order to get the middle element of both rows and columns, we would need to divide the actual length of an axis by 2, which would mean that the origin point would be at (

row.length/2

,

col.length/2

) — however, we know that both the rows and columns were set to

AXIS_LENGTH * 2

, therefore, the origin should be at (

AXIS_LENGTH

,

AXIS_LENGTH

) which would translate to

graph[5,5]

.

We can use the same logic to translate a coordinate on a real-world graph into our grid by adding the

AXIS_LENGTH

to its x and y values.

e.x. If you were to fetch the location of coordinate (3, 4) in a graph where

AXIS_LENGTH = 5

you would need to add the

AXIS_LENGTH

to each coordinate point to identify this position on our 2D grid, therefore you would find your actual coordinate at (3 +

AXIS_LENGTH

, 4 +

AXIS_LENGTH

) which would be (8, 9). As you can see below, the coordinates of point β read (3, 4) when you consider its location along the x and y axes, but its actual position in our 2D array is at

graph[8][9]

.

Pseudocode

Now that we’ve established the coordinate system in our grid, we can explore the practical aspects of our solution.

1. First, you will need to create your data structures.

A 2D

Boolean

grid is the primary data structure and will be used to maintain a record of where the character visited — so as to avoid duplicates. An

ArrayDeque

is used as a

Stack

(I know its a double-ended queue, but for the sake of simplicity I’m going to call it a

Stack

) to maintain a record of the last visited locations of the character. This will be the main driver of the iterative loop. An

ArrayList

is used to maintain the list of possible directions that a character can move in at any given coordinate.

2. Before we start the iterative loop, we need to establish the origin point of the character. For this purpose, we will push the point of origin to the

Stack

and set the origin point in the grid to true.

3. We can now start iterating the

Stack

to fetch the last known positions of the character in order to move it in the directions specified by the

ArrayList

.

4. As and when you find a new safe coordinate to move to, increment the counter, mark it as visited and push this location to the

Stack

so that we can continue the iteration.

Once the character has moved to every possible coordinate in our grid there will no longer be any last known locations in the

Stack

(since we pop them before we compute new positions), which brings us to the end of our iterative loop.

Your

area

variable will now contain a count of all the safe locations in the grid.

Code

Final Thoughts

For some reason as long as the threshold value is constant and the length of the axes is above 1,000 the final count will always be the same — so there might be a mathematical concept to help solve this with an O(n) complexity without over-engineering it as I did.

You should be able to adapt this to a Dynamic Programming solution by migrating the iterative logic to a recursive method, but I personally find this approach to be both simplistic and readable.