need help to fix this function

[mental dune]

so i have to write a function that given a type of matrix/graphs that rapresent a sort of a labirynth and a starting position calculates the shortest path to an exit.
the exit are placed along the edges of the matrix and the starting point cannot be used as an exit.
the function is working but gives most of the times the wrong result anyone have any suggestion on how to fix it

[fair narwhal]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

How to Format Code on Discord

Markup

```cpp
int main() {}
```

Result

int main() {}

Note: Back-tick (`) not quotes (')

[kindred cosmos]

Well, since you are using BFS, when you get to the end position you will have the shortest distance to the end. Therefore you can end the search one you get to the exit. The shortest path will be the value stored in the dist array on the exit position.

If you need the path you can also start from the exit and check for a nearby node/position that has a distance lesser by 1 than the value/distance stored in the current node.

Also, since you are talking about a labyrinth you should also make sure that you are not walking inside of a wall.
I recommend updating the new node check to take that into account.

Though I don't understand why you used the last 2 for loops. The implementation of BFS looks good to me

[mental dune]

sorry that was the wrong code

in this one i make sure that the cells that ar near the starting position are free and are not walls

sorry for my english but im not a native speaker

[mental dune]

and sorry i dont need the path i just need to know what is the smallest amount of 'steps' that i have to make to arrive to the nearest exit

[kindred cosmos]

Is the graph necessary for this problem? Because a std::vector<std::string> should be enough to represent the labyrinth.

And you can use the algorithm from the first message. But you will have to edit this line: if (newr >= 0 && newr < m && newc >= 0 && newc < n && quadro[newr][newc] == 1 && dist[newr][newc] == -1)
To check that the character at newr and newc is equal to ..

[kindred cosmos]

Also, in this implementation there is no need for these two checks:

if (quadro[i][j] != '+'){
if (quadro[i][j] == '.'){
  // code
}
}

You can only check:

if (quadro[i][j] == '.'){
  // code
}

[mental dune]

the professor suggested us to use a graph a +nd to be honest im more confortable with it

[mental dune]

oko thank you

[kindred cosmos]

If the graph is required, I guess you can try printing the labyrinth and the distance vector to see where there are any miscounts.

[mental dune]

oh i didnt notice that thats basically a repetition of the same thing

[mental dune]

okok i'll try

[kindred cosmos]

Ideally there should be no skipping of values. So you can't have a neighboring node that has a distance greater by more than 1

And it's good to have a distance equal to -1 inside of walls

The graph seems to be constructed properly (creating vertices to all directions from each node). I would assume that something is not good inside of the BFS implementation.

[kind blade]

!f

[fair narwhal]

#include <queue>
#include <vector>
#include "graph.h"
#include "hwk1.h"

int cambiaLivello(std::vector<std::vector<int>>& quadro,
                  std::pair<int, int>& entrata) {
  int m = quadro.size();
  int n = quadro[0].size();

  if (entrata.first <= 0 || entrata.first >= m - 1 || entrata.second <= 0 ||
      entrata.second >= n - 1) {
    return -1;  // L'entrata è sul bordo, non può essere un punto di uscita
  }

  std::queue<std::pair<int, int>> q;
  q.push(entrata);

  std::vector<std::pair<int, int>> directions = {
      {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  std::vector<std::vector<int>> dist(m, std::vector<int>(n, -1));
  dist[entrata.first][entrata.second] = 0;

  while (!q.empty()) {
    auto curr = q.front();
    q.pop();
    int r = curr.first;
    int c = curr.second;

    for (const auto& dir : directions) {
      int newr = r + dir.first;
      int newc = c + dir.second;

      if (newr >= 0 && newr < m && newc >= 0 && newc < n &&
          quadro[newr][newc] == 1 && dist[newr][newc] == -1) {
        dist[newr][newc] = dist[r][c] + 1;
        q.push({newr, newc});
      }
    }
  }

  int shortestDistance = -1;

  // Cerca la cella sul bordo più vicina escludendo l'entrata
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
          (i != entrata.first || j != entrata.second) && dist[i][j] != -1) {
        if (shortestDistance == -1 || dist[i][j] < shortestDistance) {
          shortestDistance = dist[i][j];
        }
      }
    }
  }

  return shortestDistance;
}

zVizz

Formatted by Arshia Aghaei

[kind blade]

That code was really hard to read tbh

[kindred cosmos]

Also, just keep in mind that dist[i][j] stores the shortest distance from the source node to node i, j

[kind blade]

Not entirely sure what's the definition of the wall in the code but probably wanna check these elements
[i+-1][j+-1]

for each [i][j] element

[kindred cosmos]

That's probably no longer the code that's in use

[kind blade]

Yeah I noticed it a tad bit late

[kind blade]

But I was looking at the correct code when I said this

[kindred cosmos]

I guess that anything that is . is an explorable node. When the graph gets constructed it seems like the walls are ignored so all nodes nodes should have neighbors that are not walls

So in the distance array there should be the shortest distance to any node after BFS ends

[mental dune]

yes sorry basically the matrix given in input is formed by a serie of '.' and '+' the '+' rapresent the walls

[kindred cosmos]

The only thing that needs to be checked is that the specific neighbor that is being accessed has not been visited previously

[mental dune]

#include <vector>
#include "graph.h"
#include "hwk1.h"
int cambiaLivello(std::vector<std::vector<char>>& quadro, std::pair<int,int>& entrata) {
    //inizializzo le dimensioni del grafo
    int m=quadro.size();
    int n=quadro[0].size();
    Graph graph(m*n);

     
    for (int i=0; i<m; ++i){
        for (int j=0; j<n; ++j){
            if (quadro[i][j] == '.'){
                if (i>0 && quadro[i-1][j] == '.'){
                    graph.addEdge(i*n+j, (i-1)*n+j);
                }
                if (i<m-1 && quadro[i+1][j] == '.'){
                    graph.addEdge(i*n+j, (i+1)*n+j);
                    }
                if (j>0 && quadro[i][j-1] == '.'){
                    graph.addEdge(i*n+j, i*n+j-1);
                }
                if (j<n-1 && quadro[i][j+1] == '.'){
                    graph.addEdge(i*n+j, i*n+j+1);
                }
            }
        }
        }
        //determino la posiione di entrata nel grafo
        int posizioneEntrataGrafo= entrata.first*n+entrata.second;

        //uso la BFS per trovare la cella sul bordo piu' vicina
        std::vector<int> distanze = breadthFirstSearch(graph, posizioneEntrataGrafo);
        int passiminimi= -1;
        for (int i=0; i<m; ++i){
            for (int j=0; j<n; ++j){
                if((i==0 || i==m-1 || j==0 || j==n-1) && (i!=entrata.first || j!= entrata.second) && distanze[i*n+j] != -1){
                    if (passiminimi==-1 || distanze[i*n+j] < passiminimi){
                        passiminimi=distanze[i*n+j];
                    }
                }
            }
        }
        return passiminimi;
    }```

sorry guys but what about this one

cause i think it written better

in this one i check every time if the nearby node is free

but still most of the time it gives the wrong answer

i have a doubt in the last part where it calculates the amount of steps needed

maybe if i use a dfs instead of a bfs i can write that last part better but idk

[kindred cosmos]

Looks much better. Well the amount of steps needed to get to position i, j is distanze[i][j]. In your case distanze[i*n+j] which should be correct assuming that breadthFirstSearch(graph, posizioneEntrataGrafo); returns the smallest distances to all nodes. Also, make sure that you are not checking the start node.

[mental dune]

and sorry if most of the variables/functions are named in italian

[kindred cosmos]

distanze[i*n+j] != -1 can probably be turned into distanze[i*n+j] > 0

[mental dune]

i'll change that

[kindred cosmos]

And passiminimi is initialized to -1. But you can initialize it to a really high number instead.

Or you can initialize it to labyrinthWidth * labyrinthHeight since it will probably never be higher than that

This way you will no longer need to check for passiminimi==-1 || distanze[i*n+j] < passiminimi

[mental dune]

but isnt the starting node already checked since in the last part i request that i and j mustnt be the starting position?

[kindred cosmos]

And if you want to return -1 if no shortest paths are found, you can check if that number has remained the same right before the return.

[mental dune]

but i need the function to return -1 if i cant find a way out

[kindred cosmos]

Oh, I just noticed this (i!=entrata.first || j!= entrata.second). Yes, you no longer need to check if it's the starting node.

[mental dune]

oh okok

but the fact tha i initialized it a -1 doesnt make a big difference right?

[kindred cosmos]

It will slightly increase the readability. Both approaches are fine

[mental dune]

so basically the code is right

[kindred cosmos]

Since the first time you notice an exit you save it into the distance

[kindred cosmos]

Looks right to me. I didn't run it into a compiler though

[mental dune]

cause when i upload it the professor runs a bunch of test on it and most of the times it gives the wrong output

and everything seems right to me

[mental dune]

i'll change it then thank you

[fair narwhal]

@mental dune Has your question been resolved? If so, type !solved :)

[kindred cosmos]

I'll also start implementing my approach at this problem and I will send it here

If that's okay with you

[mental dune]

int passiminimi= 999;
        for (int i=0; i<m; ++i){
            for (int j=0; j<n; ++j){
                if((i==0 || i==m-1 || j==0 || j==n-1) && (i!=entrata.first || j!= entrata.second) && distanze[i*n+j] != -1){
                        passiminimi=distanze[i*n+j];
                    
                }
            }
        }

        int risultato;
        if (passiminimi==999){
            risultato = -1;
        }
        else{
            risultato = passiminimi;
        }
        return risultato;
        ```

like this?

[mental dune]

not at all

jkjk

youre doing me a big favour

since this assignement is also due at midnight

[kindred cosmos]

If you have questions about any part of the code feel free to ask.

I also didn't do a graph-like implementation because to me it seems like it's overcomplicating the problem for no reason. (from my perspective)

The code can of course be optimized further, especially in the findMinDistToExit function. For example you can store the exit locations into a vector while building the labyrinth then just parse through it and check for the distances at those positions.

Of course you can also make the bfs function return the distances array directly and you can just do std::vector<std::vector<int>> distances = runBFS(labyrinth, startingPosition);

[mental dune]

if you could do a quick explanation on just the bfs function that, if i understood correctly, also saves all the dinstances in a vector? and the function to find the min distance

also when finding the min distance you're considering that you can move from one cell to another even if they share just a corner?

cause i forgot to add that u can move to one cell to another just if they share a side

@kindred cosmos

[kind blade]

so wherever you find an [i][j] element check where's the next [i+-1][j+-1] element that's also a +

[kindred cosmos]

When I find the min distance I only check the edges (since you mentioned that the exits are along the edges)

When I find an exit I check if the distance in the distances vector is valid, and if yes, I try to save it into the bestDistance variable which stores the shortest distance to an exit.

[kindred cosmos]

Yes, the bfs function will save all distances to the distances vector. It does that to create a path map or marking of distances or whatever you want to call it. Basically after running bfs in the distances vector you will have the shortest distance to ij

[kindred cosmos]

Yes, that's why the only possible directions (or edges if you want to consider a graph) are to the N, S, E and W (up, down, right, left)

Of course you can modify this program to move diagonally or to even skip squares. For example by modifying the directions vector you can emulate the movements of a rook from chess (if you somehow need that)

[kindred cosmos]

BFS will find the shortest distance (counted in edges traversed) to all nodes by default. There is no need to make any changes to it because the resulting distance vector will have all minimum distances to all nodes (points in the matrix/labyrinth)

The naming of findMinDistToExit is quite bad, I should have probably names it findClosestExit or something

Because that function only finds closest exit compared to the starting point (distance wise)

[mental dune]

thank you so much

i got two more questions tho

how does this program find out if a position inside the matrix is available or not, like how does it recognize that there's a wall o not?

[kindred cosmos]

Also, you can visualize BFS by thinking of burning a piece of paper (expands in all directions equally), or pouring water into the maze (will go to all neighboring nodes similarly to how a piece of paper is burnt and will also not go back)

[mental dune]

that is way more understandable than how my professor explained it tbh

[kindred cosmos]

It firstly checks if the new position if within the bounds of the matrix. That means that it's not less than 0 or higher than the width or height.

[mental dune]

and is it possible to create a function that takes in input just the matrix and the starting point and returns the min distance

that's probably a dumb question but im tired and cant think of it

[mental dune]

that's the isinbound function right?

[kindred cosmos]

The second thing that has to be verified is if the new position is not a wall. You defined walls as being + and any available/walkable surfaces as being .. Therefore you can either check if the character in the labyrinth array is not + or if it is a .. This can change depending on the problem statement. For example if you add spike traps and they are marked with w but the player can still pass through them at the cost of health points or something. You may have to check that the character from the labyrinth vector is not + (less checks, you have 1 check compared to 2 checks)

[kindred cosmos]

Yep, that's correct

The third thing that we also want to check is that we have not visited that node/element in the matrix. Since we rewrite the distance every time we take a step, then the only places that have not been visited will have a distance of -1. We can think of the water example. It will always move towards the dry surfaces. The wet surfaces already have water on them and are "flooded" (the water has no reason to stay in place or go back especially since we are continously pouring water down the maze on the starting point)

[mental dune]

but this fucntion doesnt check if it is a wall or not right?

[kindred cosmos]

Yes, it would be possible

[kindred cosmos]

The isInBound function does not check for walls.
This checks for walls: labyrinth[nextPosition.first][nextPosition.second] == '.'
And this checks if some area of the labyrinth has not been visited before: distances[nextPosition.first][nextPosition.second] == -1

[mental dune]

ok im just blind at this point

[kindred cosmos]

Also, this is called lee's algorithm. It uses BFS and can be easily modified into the Flood Fill algorithm (hence the example with the water)

The only modification that has to be done for it to become a fill algorithm is to remove the distances array (or replace it with another one if necessary) and mark every visited area with a desired character or a number (you are no longer doing distances[nextPosition] = distances[currentPosition] + 1, you are just doing distances[nextPosition] = 5 or whatever you need instead of that 5)

[mental dune]

int function(const std::vector<std::vector<char>>& labyrinth, const std::pair<int, int>& startingPosition, std::vector<std::vector<int>>& distances){
    runBFS(labyrinth, startingPosition, distances);
    int minDistance = findMinDistToExit (distances);
    return minDistance
}

this would be the final function basically?

[kindred cosmos]

Yep

You can also initialize distances inside of runBfs

And you will end up with:

std::vector<std::vector<int>> runBFS(const std::vector<std::vector<char>>& labyrinth, const std::pair<int, int>& startingPosition) {
    std::vector<std::vector<int>> distances(labyrinth.size(), std::vector<int>(labyrinth[0].size(), -1));
    // code
    return distances;
}

int function(const std::vector<std::vector<char>>& labyrinth, const std::pair<int, int>& startingPosition){
    const auto distances = runBFS(labyrinth, startingPosition, distances);
    const int minDistance = findMinDistToExit (distances);
    return minDistance
}

[mental dune]

so in the end the function would look like this?

i changed the name of the variables to my language

@kindred cosmos

[kindred cosmos]

Looks good

[mental dune]

ok well thank you so much for helping me

🤝🏼

and have a good night

[kindred cosmos]

No problem!

[fair narwhal]

@mental dune Has your question been resolved? If so, type !solved :)