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? Thanks a many already.