@@yonasbelay3343 just add any processed/visited coords to a set (a set of coords youve already handled) and add a check to make sure you only process a coord (aka add the coord to your queue) if and only if that coord is not in your set of coords
Thank you for this! Your videos are a ton of help. Quick question: I'm having a hard time understanding the need to convert non-0's into infinity. Would it not work if you were to just compare if mat[x][y] was greater than 0? Also, how does it know to skip over duplicates in the queue? Like when we've already encountered an Infinity that we've already pushed to the queue?
So with setting non-0’s to infinity - it’s just a way of marking them as unvisited, then any valid distance calculated during BFS will always be less than or equal to Infinity, so it guarantees the minimum distance. With the duplicates - we check if the current distance to reach a cell is less than the distance already present in the matrix. If it is, we update the distance in the matrix and move to the next cell, if it isn't, then we know we haven't found an optimal path, so we skip it. Hope this helps!
@@AlgoJS Ah gotcha! I understand setting non-0's to infinity now. Although with duplicates, I'm still a bit lost. My understanding is that when we're looking at position [0, 1, 0], it checks all adjacent directions and pushes [1, 1, 1] into the queue since it is equal to infinity. However, when we move on and look at position [1, 0, 0], the same thing happens where we check all adjacent directions and [1, 1, 1] is pushed into the queue once more since that value is still equal to infinity. This seems to happen a third time when looking at position [1, 2, 0] resulting in [1, 1, 1] appearing in our queue three times. From your explanation, you mentioned that we would not push positions into the queue that we have already looked at as the queue could end up getting too large. I feel like I might just be missing something, so correct me if i'm wrong. Thank you again for all your help!
You explained it well. This question was so unintuitive for me, i was trying bfs from the 1 and of course got tle. What was the clue that makes you realise "i need to bfs from 0's, it's much more efficient"
unless u mean he should explain why we're choosing bfs then theres no reason to explain why a queue. we're trying to implement bfs which is pretty much always done with a queue. if youre unsure of why we use bfs, its bc bfs is a very handy searching algorithm when computing "shortest paths" on a graph
BFS always uses a queue to get the values breadth-first (kind of like starting from the middle and spiraling outwards), whereas DFS uses recursion and goes all the way to the outer edge first, and makes it way back inwards
thx man this is the easiest one to understand out of all the ones that i've watched
One note is that this solution will add duplicate coordinates to the queue
this is what I noticed too, I am trying to figure out how you would stop it from doing so to increase efficiency
@@yonasbelay3343 just add any processed/visited coords to a set (a set of coords youve already handled) and add a check to make sure you only process a coord (aka add the coord to your queue) if and only if that coord is not in your set of coords
Thank you for making these videos. Keep up the good work.
No problem Ryan, will do!
This was the best explanation. Thank you!
Thank you for this! Your videos are a ton of help. Quick question:
I'm having a hard time understanding the need to convert non-0's into infinity. Would it not work if you were to just compare if mat[x][y] was greater than 0?
Also, how does it know to skip over duplicates in the queue? Like when we've already encountered an Infinity that we've already pushed to the queue?
So with setting non-0’s to infinity - it’s just a way of marking them as unvisited, then any valid distance calculated during BFS will always be less than or equal to Infinity, so it guarantees the minimum distance.
With the duplicates - we check if the current distance to reach a cell is less than the distance already present in the matrix. If it is, we update the distance in the matrix and move to the next cell, if it isn't, then we know we haven't found an optimal path, so we skip it.
Hope this helps!
@@AlgoJS Ah gotcha! I understand setting non-0's to infinity now. Although with duplicates, I'm still a bit lost.
My understanding is that when we're looking at position [0, 1, 0], it checks all adjacent directions and pushes [1, 1, 1] into the queue since it is equal to infinity. However, when we move on and look at position [1, 0, 0], the same thing happens where we check all adjacent directions and [1, 1, 1] is pushed into the queue once more since that value is still equal to infinity. This seems to happen a third time when looking at position [1, 2, 0] resulting in [1, 1, 1] appearing in our queue three times.
From your explanation, you mentioned that we would not push positions into the queue that we have already looked at as the queue could end up getting too large.
I feel like I might just be missing something, so correct me if i'm wrong. Thank you again for all your help!
You explained it well.
This question was so unintuitive for me, i was trying bfs from the 1 and of course got tle. What was the clue that makes you realise "i need to bfs from 0's, it's much more efficient"
you gotta show what made you decide to choose a queue.
unless u mean he should explain why we're choosing bfs then theres no reason to explain why a queue. we're trying to implement bfs which is pretty much always done with a queue. if youre unsure of why we use bfs, its bc bfs is a very handy searching algorithm when computing "shortest paths" on a graph
Btw isn't this DFS (not BFS) ?
BFS always uses a queue to get the values breadth-first (kind of like starting from the middle and spiraling outwards), whereas DFS uses recursion and goes all the way to the outer edge first, and makes it way back inwards