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 29 2 5 33 3 1 14 8 2 7In 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 width2 5 2 2  //2 2 7 3  // the3 1 2 2  // grid4 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?
Shortest path in a grid between two points
c++;optimization;algorithm;pathfinding;breadth first search