CODEWITHSUNDEEP
c++
aura
aura

Reputation: 11

Using BFS to find the shortest path

As the tittle says, I'm trying to find the shortest path for a unit to move to the neareast control point (just as if it was a treasure or something). I was trying to use the BFS to found this path but it don't give the shortest one. For exemple:

If we have something like this(where X is the starting position and K is one Control Point)

· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · X · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · K · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·

My code gives this path:

· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · - - - · · · · · · ·
· · | X | · · · · · · ·
· · | | - · · · · · · ·
· · | · · · · · · · · ·
· · | · · · · · · · · ·
· · · | · · · · · · · ·
· · · | - K · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·
· · · · · · · · · · · ·

But I don't see why it give me those extra moves. Someone can tell what i'm doing wrong?

typedef pair<int,int> Coord;
typedef vector< vector<bool> > VIS; 
typedef vector<vector< Coord> > Prev;
const int X[8] = { 1, 1, 0, -1, -1, -1,  0,  1 };
const int Y[8] = { 0, 1, 1,  1,  0, -1, -1, -1 };


list<Coord> BFS2(int x, int y, VIS& visited, Prev& p) {
    queue<Coord> Q;

    Coord in;
    in.first = x; in.second = y;

    Q.push(in);
    bool found = false;
    Coord actual;
    while( not Q.empty() and not found){   
       actual = Q.front();         
       Q.pop();
       int post = who_post(actual.first, actual.second); //It tells if we're in a control point or not(0 == if we are not in the C.point)
       if(post != 0){
          found = true;                
       }
       else {
           visited[actual.first][actual.second]=true; 
           for( int i = 0; i < 8; i++){
                  int nx = X[i] + actual.first;      
                  int ny = Y[i] + actual.second;
                //The maze is 60x60, but the borders are all mountains, so we can't access there
                if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){
                    Coord next;
                    next.first = nx; next.second = ny;
                    Q.push(next);
                    p[nx][ny] = actual;
                }
            }
        }
    }
    list<Coord> res;

    while(actual != in){
        res.push_back(actual);
        actual = p[actual.first][actual.second];
    }
    res.reverse();
    return res;
}

Upvotes: 0

Views: 289

Answers (1)

Josh Curtis
Josh Curtis

Reputation: 11

I think it has to do with how you are calculating our previous matrix. Specifically the following code

 if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){
     ...
     p[nx][ny] = actual;
 }

You update the previous matrix whenever you come across an uninvited node with the node that you are currently exploring. However, consider what happens when you start. You'll enqueue every point around where you start and mark the previous matrix for each node as the starting point. Now you'll explore some other node. Each of it's neighbors will be enqueued except for the starting point since none of them have been visited. Some of the entires in the previous matrix will be overwritten. This is why your paths don't make sense.

Upvotes: 1

Related Questions