Hi, everyone, welcome to this new video.
So, as discussed, we are going to do so, we are going to write the code for solving this problem
and we discussed that.
I'm going to use them so I can be efficient, go to them.
We need one visitor today.
We need one Giulietta structure.
Right.
So that is the basic thing that we need to implement the algorithm before writing the code for the BFX.
Let's first define what is one cell, right?
Let's first define what is one cell.
So a cell will contain two things.
What is the coordinate, extraordinary divide coordinate and what is the distance rate?
What is the distance?
So it will contain two things.
A cell will contain three things.
So let's start writing the code for the cell.
We need to define what cell is.
Struct cell, or you can write class also, so we need to define the X calling it, what is the Y coordinate
for the cell and what is the distance?
Rate settings, what is the distance?
So what do I mean by distance, so by distance I mean that, yes, so by distance I mean that.
So this distance is one, this distance distances to this distance three, and this is distance for
late.
So this cell will contain distance when this cell will contain distance to this cell, will contain
distance tree and this cell will contain distance for.
So I am calculating this distance from the first box.
Right.
And for the first box I need to initialize the distance by one because by one means because it it is
containing one zero right there.
So I will initialize it to one and not zero.
Similarly when I will come here.
So I what I will do, I will do distance placeless so from when it will become two.
Similarly from here I will come here and this distance too will be incremented to distance three.
Similarly from this I will come here and it will be commanded to the Senate for finally what I am going
to do.
I am going to return the distance for this thing late.
So that is the approach that I am going to take.
And we remember that we can move in either directions, we can move in each direction, so let us create
one area I can move in either direction.
So X coordinate of those eight directions and the Y coordinate of those introductions, so I'm standing
here, right, let's say I'm standing at this.
So what are the directions this, this, this, this, this, this, this and this.
So first, let's talk about the X coordinate.
So here the X coordinate will reduce by one minus one had the X coordinate will reduce by one minus
on here it will remain same.
So zero here.
The X coordinate will increase by one.
So we had the X coordinate minus one.
I'm standing here and there.
The X coordinate will become plus one.
Similarly this is minus one.
This is same X coordinate and this will become plus one.
So let's first write all these values here, minus one, then zero.
Then I have one plus one that is and a minus one.
Then I have one, then I have minus one, then I have zero, then I have one.
So these are the X coordinates, right.
So now let's talk about divide coordinates.
So I am here.
Right.
So for y coordinate this will be minus one.
That is correct.
This will be minus one for Y coordinate and this will be minus one.
So here it will be zero.
No change in Y and here it will be plus one plus one plus one plus one.
So these are divided coordinates value.
So if I'm going up then this will be minus one, minus one and minus one.
So for the same level zero and zero.
And if I'm going down this would be one one and one.
So we have so we can move in their direction, that why I am doing this right, we can move in a direction.
So that's why we need to find out the X and Y coordinate changes the incentive change next.
What is the X change in X, difference in X and difference in Y right now?
After that, what we need to do, we need when we're ready.
So this visiting area will be at a rate so predictable.
This is our it is today and it is given that the grid is off size and so grid size and cross and grid
is of size and cross.
And so I need to create one visitor that he throws and and we need to initialize this area by a false.
So what am doing here, this is our grid, I am creating one visitor to L.A. and initially all the value
will be false.
No element is visited.
So a false, false, false, right.
False here, Voltaire, false, false, false and false.
So this is the syntax for doing that.
Simple.
Now what we'll do, we will push this starting vertex in our queue.
So we need to push the starting vertex in our queue.
So first of all, we need to create queue of integers.
You and we need to push the starting.
We need to push the starting vertex, the source vertex.
So sorry, this will be queue of cell rate.
You will contain one cell.
So that will be key off cell.
So first cell.
What is the expert in it?
Zero.
What is the Y coordinate zero.
And what is the distance distances.
One.
Right distances when so I have discussed this is one cell queue will contain one cell and for this cell,
what is the extraordinary digital what is the record and zero and what is the distance distances when
it is containing?
I am encountering one zero.
That's right.
When.
Right.
So since I have visited this vortex, that is I have pushed this vertex in the queue.
So what I will do, I will mark this as visitor that I have visited.
This so visited of 090 zero is proof.
I have visited the source cell source vertex.
Right.
And now what do we have?
We will have the standard loop, right.
While the queue is not empty, while the queue is not empty.
So what we are going to do is let's pop one cell therapy or temp.
So cell temp is basically called out front.
And then what we are going to do is dude artpop simple.
So let's check here.
So if the content of this cell is equal to and minus one and the Y coordinate of this cell is equal
to and minus one, that is I have reached the last cell.
So if I have reached the last cell, I am going to return that distance for this sorted out distance
rate.
So what I am doing here is I am checking the X coordinate of the cell and by coordinating the cell.
So if the X coordinator of the cell and via coordinate of the cell is corresponding to this box, then
what I need to do, I just need to return the value so I am returning the value I'm returning for.
Right.
So if this is not the case, if this is not the case, if I am not standing at the last cell, then
from the given cell, I can move in either directions so I can move in either direction.
So I equals zero i.e. less then eight I plus plus I can move in a direction.
So what will be the new X coordinate.
New X coordinate will be the original X coordinate plus the change in X direction.
Similarly, what will be the Y coordinate, so y coordinate will be the original Y coordinate the cell
where I'm am standing, let's the change in y coordinate.
Right.
So this is so what I'm doing here.
I'm standing at this and.
Right.
I am standing at this cell.
So this is the X Guardian in the Y coordinate so I can move in either direction from this cell.
Right.
I can move in each direction.
So what I'm doing, I'm calculating the new one, basically the new X and Y coordinate.
So from this cell, the original X coordinate plus the change in each direction, similarly the change
in direction, similarly the change in direction, the change in direction.
So that is what I am doing.
Right.
I am finding out the new X and Y coordinate, so I am finding out the new X and Y coordinate and what
I will do, I will push this new X and Y coordinate into the Q So what is the new X according that this
is X and Y and what is the distance distances.
The dart distance plus one.
See what I'm doing here?
I told you so for this, the distance is one for the distances too.
So I'm standing here.
If I will go ahead, but I will do I will increase the distance by one.
I will do distance plus plus rate.
So I'm increasing the distance, my distance plus one.
Right.
So we cannot directly do this.
Right, because first we need to check whether X is a valid coordinate or not vice valid coordinate
or not.
Similarly, X and Y should contain zero right in our kill.
Our cue will only contain zero hour will not contain one because we are only interested in.
So we need to find out the shortest path and I can only move along as it was not once before.
Doing this, I need to write few if condition that we need to check the validity with X and Y is a valid
coordinate or not.
So for checking the validity, what are the conditions that we need to write to?
First of all, X must be good in order close to zero then only it is a valid coordinate.
Right.
And X must be less than ten then.
Then it is a valid coordinate.
Similarly, V must be greater than or equal to zero and Y must be less than.
And and.
We need to check whether this X coordinate and Y coordinate is containing one or zero, so it must contain
zero that we will only move along zero.
So it must contain zero.
And this cell must not be visited.
Right.
That's why we have it ready.
So this cell that is X coordinate and why coordinate.
So this cell must not be visited before then.
Only I will visit this.
So I will visit this, and since I have pushed this into our queue, what I need to do, I need to mark
this as a visitor.
I need to mark this cell as visited.
So visitors of x ray is a close to two.
Right.
And that that will be the complete code.
And finally, what you are going to do is when your kid will become empty and you are not able to reach
the last index, so you will return minus one.
Right.
So we are returning our answer here.
But if we are not able to reach the last index, then our answer will be minus one.
Right.
So that is the complete goal.
One more thing, let's check a few basic conditions here before we are writing our code.
So basic condition is if the first cell of the Matrix, if the first cell of the graph is containing
one, that means there will be no answer.
Right, if the first box is containing one.
So if this first box, instead of containing zero, if the first box is containing one, then the third,
you will directly return, minus one you cannot reach here.
So if the first is containing one, then done minus one that.
So that will be the code for solving this problem.
So let's see.
Let's try to run our code and let's see whether our code is correct or not or it has some bugs.
So here, yep, and I need to write semicolon.
Yep, so let's try to sum our gold.
Yeah, so basically, our court is working fine, right?
So that will be the complete code and let us discuss the time and the space complexity.
So complexity is very obvious.
You are creating one visitor at a rate of size and gross.
And so this will be the time, complexity, sorry, space, complexity, big off and square.
Now, let's talk about the time complexity.
So in time, complexity, what we are doing, so we are trading or work to date, we are trading overkill.
So in the worst case, how many elements of representing you?
So if my matrix is containing zeros, all zeros, so time complexity will be we will go through each
and every element once the time complexity is big off and square.
So this is the time and the space complexity for this problem.
Right.
And this is the entire code, very simple write simple BFW algorithm.
So this is all about this device.
If you have any doubt in this problem to ask me, I will see you in the next one.
Thank you.