# Shortest path in a grid between two points

I have this problem where I have to find the shortest path in an NxM grid from point A (always top left) to point B (always bottom right) by only moving right or down. Sounds easy, eh? Well here's the catch: I can only move the number shown on the tile I'm sitting on at the moment. Let me illustrate:

2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7


In this 4x4 grid the shortest path would take 3 steps, walking from top left 2 nodes down to 3, and from there 3 nodes right to 1, and then 1 node down to the goal.

[2] 5  1  2
9  2  5  3
[3] 3  1 [1]
4  8  2 [7]


If not for the shortest path, I could also be taking this route:

[2] 5 [1][2]
9  2  5  3
3  3  1 [1]
4  8  2 [7]


That would unfortunately take a whopping 4 steps, and thus, is not in my interest. That should clear things out a bit. Now about the input.

The user inputs the grid as follows:

5 4      // height and width
2 5 2 2  //
2 2 7 3  // the
3 1 2 2  // grid
4 8 2 7  //
1 1 1 1  //


So what have I done? I figured the best way around this (to begin with) would be BFS. Voila, correct answer on every input. Hurray, it's too freakin' slow.

Anyway here's the code at the moment:

#include <iostream>
#include <vector>

struct Point {
int y, x, depth;
Point(int yPos = 0, int xPos = 0, int dDepth = 0) : y(yPos), x(xPos), depth(dDepth) { }
};

struct grid_t {
int height, width;
std::vector< std::vector<int> > tiles;

grid_t() // construct the grid
{
std::cin >> height >> width; // input grid height & width

tiles.resize(height, std::vector<int>(width, 0)); // initialize grid tiles

for(int i = 0; i < height; i++)     //
for(int j = 0; j < width; j++)  // input each tile one at a time
std::cin >> tiles[i][j];    // by looping through the grid
}
};

int go_find_it(grid_t &grid)
{
std::vector<Point> openList, closedList;
openList.push_back(Point(0, 0)); // (0, 0) is the first point we want to consult, of course

do
{
closedList.push_back(openList[0]); // the tile we are at is good and checked. mark it so.
openList.erase(openList.begin()); // we don't need this guy no more

int y = closedList.back().y; // now we'll actually move to the new point
int x = closedList.back().x; //
int depth = closedList.back().depth; // the new depth

if(y == grid.height-1 && x == grid.width-1) return depth; // the first path is the shortest one. return it

int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.
grid.tiles[y][x] = 0; // mark the tile visited

if(y + jump < grid.height && grid.tiles[y+jump][x] != 0) // if we're not going out of bounds or on a visited tile
{
openList.push_back(Point(y+jump, x, depth+1)); // push in the new promising point along with the new depth
}
if(x + jump < grid.width && grid.tiles[y][x+jump] != 0) // if we're not going out of bounds or on a visited tile
{
openList.push_back(Point(y, x+jump, depth+1)); // push in the new promising point along with the new depth
}
}
while(openList.size() > 0); // when there are no new tiles to check, break out and return false

return 0;
}

int main()
{
grid_t grid; // initialize grid

int min_path = go_find_it(grid); // BFS

std::cout << min_path << std::endl; // print the result
//system("pause");
return 0;
}


So what I want is some optimization hints, because I suck at it (and am relatively new to C++). Basically jumped into it a month ago with only as much knowledge from PHP and javascript). Should I make it A* instead of BFS? If I did that, how would I calculate the heuristic?

-
always right or down, always the total amount the case value is at? so it should be very fast : on each step, try both directions: try_right (goes N right, and also store "R" in the current result string), and try_down (goes N down, and stores "D" in the result string). And if you reach exatcly the bottom-right end: keep_result (keeps the current result_string if it is shorter than the previously stored). Otherwise (we go > down or >right than bottom left?) discard current result. –  Olivier Dulac Jan 4 '13 at 16:34
tricky part in my solution is to keep track of progress, to explore it all. Recursivity should help (beware you have separate current strings for each path) –  Olivier Dulac Jan 4 '13 at 16:37
in your case example, it is easy to see there are only 2 routes. On a much bigger case, it could grow quite a lot, but still: on an X/Y tile, you can only progress toward the bottom right at least 1 step (right, or down) : you can't have more than (max(heigth,width)) steps overall in your final solution. If (worst case) all solutinos are at least that long (ex: all tiles contain "1"), it's trivial to compute the worst possible number of steps your algorithm will have to test to cover all possibilities –  Olivier Dulac Jan 4 '13 at 16:41
If this is a programming contest question, which it sounds like, what are the upper bounds for N and M? For a 100000 X 100000 grid of all 1s will take a lot of time with a naive solution. –  abuzittin gillifirca Jan 4 '13 at 17:29
1000x1000 is the upper bound –  Olavi Mustanoja Jan 4 '13 at 18:13

1. profile it!
2. it's a good choice to use a std::deque (which is the default container used by std::queue) instead of a std::vector. The potentially expensive operations (again, you should profile to confirm this) are push_back() and pop_front() (back() is likely to be constant time for almost any container)

• std::vector has amortized constant time push_back, but push_front is linear time
• NB. this is because it has to move each of n-1 items forward one space, but it does not have to reallocate
• std::deque has amortized constant time push_back and push_front, so is probably faster

I'm going to say it again though - you should profile both choices and verify this. Even if the asymptotic complexity is better for std::deque, the constant overhead is greater, and that could dominate depending on your data size

3. do you actually use closedList for anything? It looks like you only ever use the back, in which case you could replace it with a single Point

-
+1 remove closed list –  Emily L. Mar 19 at 10:16

I think BFS is your algorithm, but I do have some cleanups for you. The reason A* won't work is because your estimation of how much farther you have to go (you could do a simple grid distance from where you are to the end point, also considering the jump value where you are sitting) could be wrong based on future jumps, and in your case, estimations are not acceptable. (Note: in some cases, for example if this was an AI in a game, estimation can be acceptable if performance is greatly improved)

1) Use a queue instead of a vector for openList. Every erase on the first item in a vector means you have to copy all the items to new memory positions!!! BFS algorithm and std::queue are a married pair because your push and pop are constant time, and you won't accidentally push or pop at the wrong end.

2) You are keeping a list of visited points, but you aren't using this list, and you aren't using it because you don't need it. You can't go backwards in your path toward the end, so you don't have to keep track of where you have been.

-
+1 for queue. Linked list would work as well but I think queue is faster. –  Emily L. Mar 19 at 10:03
• Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.
• Dont do IO in the constructor.

- Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

-
"std::vector does bounds checking" at does bounds checking; operator[] does not. –  Corbin Jan 4 '13 at 20:42
Thanks. I stand corrected. –  abuzittin gillifirca Jan 4 '13 at 21:31