Shortest path in a grid between two points

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

struct Point

The constructor could be omitted, with small changes to the calling code:

openList.push_back({0,0,0});

        openList.push_back({y+jump, x, depth+1});

        openList.push_back({y, x+jump, depth+1});

struct grid_t

height and width are redundant.

A better structure would use a single vector of height × width elements, to give better locality of reference. Consider providing an operator()(std::size_t x, std::size_t y) to index it.

Instead of reading unconditionally from std::cin, allow user to specify a stream (don't forget explicit!). And throw an exception if reading fails - at present, a partially-read grid will be filled with zeros, without any indication of failure.

go_find_it()

Consider working backwards: from the target point to the starting point. There will be much more opportunity for pruning at each step if we only need to consider the valid jumps that land exactly on the current square.

Answer 4

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