I came across this question on 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. StackOverflow Enjoy! The Problem There is a character who can move around on a two-dimensional coordinate grid. The character is placed at point . (x,y) (0,0) From the character can move to , , , and . (x, y) (x+1, y) (x-1, y) (x, y+1) (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 plus the sum of the digits of are less than or equal to 23. abs(x) abs(y) For example, the point is not safe because 6 + 4 + 5 + 9 = 24, which is greater than 23. The point is safe because 1 + 0 + 5 + 1 + 7 = 14, which is less than 23. (64, -59) (105, -17) 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 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 length of an axis. For example, if you need the -axis to range from you will need an array of length to accommodate these coordinates where . Array 0..n x -100..100 AXIS_LENGTH * 2 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 — however, if we attempt to use these same coordinates to map the origin point in our 2D array, you’ll see that will point to the upper-left most coordinate at , 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. (0, 0) graph[0][0] (-5, -5) 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 ( , ) — however, we know that both the rows and columns were set to , therefore, the origin should be at ( , ) which would translate to . row.length/2 col.length/2 AXIS_LENGTH * 2 AXIS_LENGTH AXIS_LENGTH graph[5,5] We can use the same logic to translate a coordinate on a real-world graph into our grid by adding the to its and values. AXIS_LENGTH x y If you were to fetch the location of coordinate in a graph where you would need to add the to each coordinate point to identify this position on our 2D grid, therefore you would find your actual coordinate at which would be . As you can see below, the coordinates of point read when you consider its location along the and axes, but its actual position in our 2D array is at . e.x. (3, 4) AXIS_LENGTH = 5 AXIS_LENGTH (3 + AXIS_LENGTH , 4 + AXIS_LENGTH ) (8, 9) β (3, 4) x y 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 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 is used as a (I know its a double-ended queue, but for the sake of simplicity I’m going to call it a ) to maintain a record of the last visited locations of the character. This will be the main driver of the iterative loop. An is used to maintain the list of possible directions that a character can move in at any given coordinate. Boolean ArrayDeque Stack Stack ArrayList 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 and set the origin point in the grid to true. Stack 3. We can now start iterating the to fetch the last known positions of the character in order to move it in the directions specified by the . Stack 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 so that we can continue the iteration. Stack Once the character has moved to every possible coordinate in our grid there will no longer be any last known locations in the (since we pop them before we compute new positions), which brings us to the end of our iterative loop. Stack Your variable will now contain a count of all the safe locations in the grid. area 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 complexity without over-engineering it as I did. O(n) 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.

Fetch

DAMIAN.PERERA.IO

Read My Stories

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

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

Too Long; Didn't Read

Company Mentioned

Damian Perera

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

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

Too Long; Didn't Read

Company Mentioned

Damian Perera

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES