4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ always right or down, always the total amount the case value is at? so it should be very fast : on each step, try both directions: try_right (goes N right, and also store "R" in the current result string), and try_down (goes N down, and stores "D" in the result string). And if you reach exatcly the bottom-right end: keep_result (keeps the current result_string if it is shorter than the previously stored). Otherwise (we go > down or >right than bottom left?) discard current result. \$\endgroup\$ – Olivier Dulac Jan 4 '13 at 16:34
  • \$\begingroup\$ tricky part in my solution is to keep track of progress, to explore it all. Recursivity should help (beware you have separate current strings for each path) \$\endgroup\$ – Olivier Dulac Jan 4 '13 at 16:37
  • 1
    \$\begingroup\$ in your case example, it is easy to see there are only 2 routes. On a much bigger case, it could grow quite a lot, but still: on an X/Y tile, you can only progress toward the bottom right at least 1 step (right, or down) : you can't have more than (max(heigth,width)) steps overall in your final solution. If (worst case) all solutinos are at least that long (ex: all tiles contain "1"), it's trivial to compute the worst possible number of steps your algorithm will have to test to cover all possibilities \$\endgroup\$ – Olivier Dulac Jan 4 '13 at 16:41
  • \$\begingroup\$ If this is a programming contest question, which it sounds like, what are the upper bounds for N and M? For a 100000 X 100000 grid of all 1s will take a lot of time with a naive solution. \$\endgroup\$ – abuzittin gillifirca Jan 4 '13 at 17:29
  • \$\begingroup\$ 1000x1000 is the upper bound \$\endgroup\$ – Olavi Mustanoja Jan 4 '13 at 18:13
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Actually, it is interesting whether a point was already visited: If so, any additional route leading to it is uninteresting, as it cannot be shorter. Just zeroing the distance one can travel from there is better than making a separate list though. \$\endgroup\$ – Deduplicator Oct 15 '18 at 12:43
4
\$\begingroup\$
  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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$
  • 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ "std::vector does bounds checking" at does bounds checking; operator[] does not. \$\endgroup\$ – Corbin Jan 4 '13 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.