Hi, everyone, welcome to this new video.
So in this video, we are going to solve this question shortest path in a binary matrix.
So we are given a binary matrix that means zeros and ones.
So if this is my matrix, it will contain zeros and ones.
I am standing at the first box and I want to reach the last box and I need to return this shortest path.
But there is one condition and the condition is basically since the binary matrix, it will contain
zeros and ones.
You can only move two zeros, we can only move two zeros and we cannot move to one.
Right.
So that is the condition.
So all the cells of the part must contain zero and you can move in each direction from a given box.
Right.
So from a given box, we can move in either directions.
Right, and we need to find out the length of a clear path, a clear path means the path in which you
have Xeros only zeros and not ones.
So let's take a few example and let's try to understand.
So let's talk about the first example which is given in the question.
So here it is very clear that the answer will be too late.
It will start us standing here and you want to reach here.
So how many zeros you visited?
You visited toolbox, right?
That's right.
The output is two.
So if we visualize this matrix as a graph, then how will the graph look like?
So let's name these nodes A, B, C and B, so I have this node A and it is containing zero.
So from E, I can go to B, C and I can go to B, which is containing one I can go to see which is containing
one and I can go to the which is containing zero.
And obviously from C I can go to eight also from B I can go to able to from the.
I can go to to.
So that's why these will be by-election.
And so I am visualizing Matrix as a graph.
Right.
So in this graph this is my graph.
And what is the longest.
Sorry.
What is the shortest part.
The shortest battle with this one.
Right.
I'm talking about the spot.
So how many zeros I visited.
I visited two zeros.
So the output is two.
So can we solve this question using best algorithm?
Yes.
B, if this algorithm is used to find out the shortest path in a graph.
So basically, Vadum is used to find out shortest path in a graph.
And here in this question, we need to find the shortest path.
So BFC algorithm is the perfect algorithm for solving this problem.
Let's take one more example.
Let's try to see one more example and let's see.
So here in this example, I can see.
So from here I am going at this box now from this box, I had two options.
I can go here as well as here, but we need to find out the shortest path that.
So I will come here and then from this I will come here.
So how many zeros I visited for zeros that tied the output is four.
For in this case, the first box is basically one, right, one zero zero.
Then I have one one zero, then one one zero.
So the first box is containing one.
It should be zero.
Right?
So that's why the output is minus one.
I cannot move to the box, which is containing one.
So in this case, there is no short list.
But so that time minus one.
So here in this example, let's see how the algorithm will help us.
So I told you what we need to do.
We need to visualize grid as our we need to visualize Matrix as a graph.
So this is ABC.
The F and G.
So let's talk about Nordea, this is our Nordea, so from not a I can move to not be, which is containing
zero, so not is also containing zero.
I can move to Nordea, which is containing one, and I can move the node, which is also containing
one.
So similarly, these are bidirectional edges.
Right.
So now let's talk about this node.
So from B I can go to see which is correct.
C is containing zero from B. I can also go to D so I can also go to the and vice versa from B, I can
also go to E and vice versa.
I can go to E and vice versa.
So yep.
Now from B I can also go to F, I can also go to F which is containing zero.
Right now, let's talk about a half hour.
First, let's talk about C. So from C. I can go to F, I can go to B, I can go to E.
Now, let's talk about, if so from if I can go to B, I can go to from F, I can go to E, B, C,
I, and so I can go to IHI, which is containing Xeros.
And many of the notes, right, and the rest of the graph, we are only interested in the truth, so
I'm not considering one.
So this is our graph and we want to find out the shortest part starting from this node.
And I want to reach this node.
Right.
This is the last one.
All right.
I want to reach this node.
So which algorithm can help us here?
Best algorithm, because BFW algorithm is used to find out the shortest path in a graph.
Beerfest algorithm is nothing but the level that I drivers in the laboratory that we used to do in trees.
So Beerfest is nothing, just the louder traversal.
So this is your first level.
This is your second level.
This is your third level.
And this is your fourth level.
Since this is the fourth level.
That's why the output is four.
Right.
So BFW algorithm is the perfect algorithm for solving this problem, for finding out the shortest path.
So whenever you encounter one problem and that problem is asking you to find out the shortest part,
there are two directions.
First one is using the grid approach.
Grid approach will not work.
Second approach you can think of finding the shortest path is using dynamic programming that also will
not work here.
And the third option, so you can think of BFX whether BFW will work or not.
So BFW will work in this problem.
Right.
So in NextRadio, what I'm going to do is I'm going to write the code for the BFC algorithm.
So I highly recommend that before watching the next video, you should try to write the code for this
problem yourself.
Right.
And obviously in the next video, you can see my solution.
So that is a device that is all about this video.
I will see you in the next one.
Thank you.