I recently encountered this dynamic programming problem and I wanted to see if anyone had thoughts on the approach to solve this. I had a hard time with this, and it's probably because I got stuck in the thinking of creating a huge tree to handle all of the possibilities.
The Problem
There is a character who can move around on an 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?
(319,219), (398,298)
? i.stack.imgur.com/ToNGJ.png