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 &lt;iostream&gt;
#include &lt;vector&gt;

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&lt; std::vector&lt;int&gt; &gt; tiles;

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

        tiles.resize(height, std::vector&lt;int&gt;(width, 0)); // initialize grid tiles

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

int go_find_it(grid_t &amp;grid)
{
    std::vector&lt;Point&gt; 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 &amp;&amp; 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 &lt; grid.height &amp;&amp; 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 &lt; grid.width &amp;&amp; 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() &gt; 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 &lt;&lt; min_path &lt;&lt; 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?
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)


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