12
1
Turn-based tactics games like Advance Wars, Wargroove, and Fire Emblem are made up of a square grid of varying terrain with units of differing movement classes requiring different costs for each terrain type. We'll be investigating a subset of that problem.
Challenge
Your task is to determine if one location is reachable from another given a grid of terrain costs and a movement speed.
Units can only move orthogonally where the cost of moving onto a square is the value of the corresponding cell on the grid (moving off is free). For instance, moving from a cell valued 3 onto a cell valued 1 costs 1 movement, but going the other way requires 3. Some squares may be inaccessible.
Example
1 [1] 1 1 1
1 2 2 3 1
2 3 3 3 4
1 3 <1> 3 4
Moving from [1]
to <1>
requires a minimum of 7 movement points by moving right one square and then down three. Thus, if given 6 or less as the movement speed, you should output a falsy answer.
Example Test Cases
These will use top-left-origin zero-indexed (row, column) coordinates rather than bracketed cells for start and end to make parsing easier. Unreachable cells will be represented with X
Case 1a
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (2, 3) to (0, 1)
Output: True
Case 1b
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 4
From (2, 3) to (0, 1)
Output: False
Case 1c
1 1 2 1 X
1 2 2 1 1
2 1 1 2 1
X X X 1 2
Speed: 5
From (0, 1) to (2, 3)
Output: False
Case 2a
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (3, 4) to (2, 1)
Output: True
Case 2b
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 4
From (3, 4) to (2, 1)
Output: False
Case 2c
3 6 1 1 X 4 1 2 1 X
5 1 2 2 1 1 1 X 1 5
2 1 1 1 2 1 1 1 X 1
2 1 1 3 1 2 3 4 1 2
1 1 2 1 1 4 1 1 1 2
3 2 3 5 6 1 1 X 1 4
Speed: 7
From (1, 8) to (2, 7)
Output: True
Case 3a
2 1 1 2
2 3 3 1
Speed: 3
From (0, 0) to (1, 1)
Output: False
Case 3b
2 1 1 2
2 3 3 1
Speed: 3
From (1, 1) to (0, 0)
Output: True
Rules, Assumptions, and Notes
- Standard loopholes are banned, I/O can be in any convenient format
- You may assume coordinates are all on the grid
- Movement speed will never be over 100
- Inaccessible cells may be represented with very large numbers (e.g. 420, 9001, 1 million) or with 0 or null, whichever is most convenient for you.
- All inputs will consist of positive integers (unless using null or 0 to represent unreachable cells)
1@LuisfelipeDejesusMunoz "These will use top-left-origin zero-indexed (row, column) coordinates" – Beefster – 2019-03-27T18:03:19.360
You say I/O can be in any convenient format. Does that include, for example, a list/array with dimensions? I believe that's typically permitted, but it definitely saves a lot of bytes over parsing a string. – dfeuer – 2019-03-27T18:57:33.943
@dfeuer, yes of course – Beefster – 2019-03-27T18:58:24.297
I downloaded advanced wars on my phone emulator... *I am so sad that it forces you to do the 13 tutorial levels...* I wanted to replay it very badly but my patience is paper thin for tutorial pandering on old systems. – Magic Octopus Urn – 2019-03-27T19:20:21.397