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
#include

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 > tiles;

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

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

for(int i = 0; i > tiles[i][j]; // by looping through the grid
}
};

int go_find_it(grid_t &grid)
{
std::vector 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'

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.

StackExchange Code Review Q#20152, answer score: 5