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

October 14th 2020 576 reads

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!

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?

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 `-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 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 *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 `AXIS_LENGTH`

`AXIS_LENGTH`

`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.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.

Join Hacker Noon

Create your free account to unlock your custom reading experience.