1
00:00:00,840 --> 00:00:02,910
Hi, everyone, welcome to this new video.

2
00:00:03,150 --> 00:00:08,490
So, as discussed, we are going to do so, we are going to write the code for solving this problem

3
00:00:08,760 --> 00:00:10,020
and we discussed that.

4
00:00:10,020 --> 00:00:13,330
I'm going to use them so I can be efficient, go to them.

5
00:00:13,360 --> 00:00:14,750
We need one visitor today.

6
00:00:15,060 --> 00:00:16,800
We need one Giulietta structure.

7
00:00:17,250 --> 00:00:17,700
Right.

8
00:00:17,880 --> 00:00:23,760
So that is the basic thing that we need to implement the algorithm before writing the code for the BFX.

9
00:00:24,000 --> 00:00:28,140
Let's first define what is one cell, right?

10
00:00:28,410 --> 00:00:30,890
Let's first define what is one cell.

11
00:00:31,140 --> 00:00:34,020
So a cell will contain two things.

12
00:00:34,230 --> 00:00:39,000
What is the coordinate, extraordinary divide coordinate and what is the distance rate?

13
00:00:39,630 --> 00:00:40,650
What is the distance?

14
00:00:41,070 --> 00:00:42,990
So it will contain two things.

15
00:00:42,990 --> 00:00:44,940
A cell will contain three things.

16
00:00:45,900 --> 00:00:48,630
So let's start writing the code for the cell.

17
00:00:49,860 --> 00:00:51,960
We need to define what cell is.

18
00:00:54,160 --> 00:01:04,180
Struct cell, or you can write class also, so we need to define the X calling it, what is the Y coordinate

19
00:01:04,180 --> 00:01:06,070
for the cell and what is the distance?

20
00:01:07,530 --> 00:01:10,050
Rate settings, what is the distance?

21
00:01:14,240 --> 00:01:22,720
So what do I mean by distance, so by distance I mean that, yes, so by distance I mean that.

22
00:01:23,000 --> 00:01:28,790
So this distance is one, this distance distances to this distance three, and this is distance for

23
00:01:29,150 --> 00:01:29,540
late.

24
00:01:29,700 --> 00:01:35,330
So this cell will contain distance when this cell will contain distance to this cell, will contain

25
00:01:35,330 --> 00:01:37,660
distance tree and this cell will contain distance for.

26
00:01:37,910 --> 00:01:41,390
So I am calculating this distance from the first box.

27
00:01:42,030 --> 00:01:42,440
Right.

28
00:01:42,560 --> 00:01:49,100
And for the first box I need to initialize the distance by one because by one means because it it is

29
00:01:49,100 --> 00:01:51,120
containing one zero right there.

30
00:01:51,170 --> 00:01:53,840
So I will initialize it to one and not zero.

31
00:01:54,800 --> 00:01:56,620
Similarly when I will come here.

32
00:01:57,440 --> 00:02:01,970
So I what I will do, I will do distance placeless so from when it will become two.

33
00:02:02,180 --> 00:02:08,660
Similarly from here I will come here and this distance too will be incremented to distance three.

34
00:02:08,840 --> 00:02:14,060
Similarly from this I will come here and it will be commanded to the Senate for finally what I am going

35
00:02:14,060 --> 00:02:14,390
to do.

36
00:02:14,390 --> 00:02:18,980
I am going to return the distance for this thing late.

37
00:02:19,130 --> 00:02:21,590
So that is the approach that I am going to take.

38
00:02:24,280 --> 00:02:32,440
And we remember that we can move in either directions, we can move in each direction, so let us create

39
00:02:32,440 --> 00:02:35,590
one area I can move in either direction.

40
00:02:41,250 --> 00:02:48,330
So X coordinate of those eight directions and the Y coordinate of those introductions, so I'm standing

41
00:02:48,330 --> 00:02:52,200
here, right, let's say I'm standing at this.

42
00:02:52,420 --> 00:02:57,780
So what are the directions this, this, this, this, this, this, this and this.

43
00:02:58,020 --> 00:03:00,660
So first, let's talk about the X coordinate.

44
00:03:00,780 --> 00:03:07,700
So here the X coordinate will reduce by one minus one had the X coordinate will reduce by one minus

45
00:03:07,710 --> 00:03:09,090
on here it will remain same.

46
00:03:09,090 --> 00:03:10,200
So zero here.

47
00:03:10,200 --> 00:03:11,820
The X coordinate will increase by one.

48
00:03:12,390 --> 00:03:14,510
So we had the X coordinate minus one.

49
00:03:14,790 --> 00:03:16,270
I'm standing here and there.

50
00:03:16,290 --> 00:03:17,860
The X coordinate will become plus one.

51
00:03:18,210 --> 00:03:20,150
Similarly this is minus one.

52
00:03:20,160 --> 00:03:22,940
This is same X coordinate and this will become plus one.

53
00:03:22,950 --> 00:03:31,500
So let's first write all these values here, minus one, then zero.

54
00:03:33,030 --> 00:03:36,990
Then I have one plus one that is and a minus one.

55
00:03:36,990 --> 00:03:46,090
Then I have one, then I have minus one, then I have zero, then I have one.

56
00:03:46,950 --> 00:03:49,570
So these are the X coordinates, right.

57
00:03:49,830 --> 00:03:52,340
So now let's talk about divide coordinates.

58
00:03:52,350 --> 00:03:53,210
So I am here.

59
00:03:54,730 --> 00:03:54,950
Right.

60
00:03:55,260 --> 00:03:59,000
So for y coordinate this will be minus one.

61
00:03:59,010 --> 00:03:59,750
That is correct.

62
00:03:59,760 --> 00:04:03,430
This will be minus one for Y coordinate and this will be minus one.

63
00:04:03,780 --> 00:04:05,120
So here it will be zero.

64
00:04:05,130 --> 00:04:11,340
No change in Y and here it will be plus one plus one plus one plus one.

65
00:04:11,520 --> 00:04:13,360
So these are divided coordinates value.

66
00:04:13,530 --> 00:04:19,820
So if I'm going up then this will be minus one, minus one and minus one.

67
00:04:20,700 --> 00:04:23,370
So for the same level zero and zero.

68
00:04:24,060 --> 00:04:29,010
And if I'm going down this would be one one and one.

69
00:04:30,670 --> 00:04:37,330
So we have so we can move in their direction, that why I am doing this right, we can move in a direction.

70
00:04:37,330 --> 00:04:43,100
So that's why we need to find out the X and Y coordinate changes the incentive change next.

71
00:04:43,120 --> 00:04:50,170
What is the X change in X, difference in X and difference in Y right now?

72
00:04:50,170 --> 00:04:53,500
After that, what we need to do, we need when we're ready.

73
00:04:54,040 --> 00:05:01,120
So this visiting area will be at a rate so predictable.

74
00:05:02,710 --> 00:05:14,860
This is our it is today and it is given that the grid is off size and so grid size and cross and grid

75
00:05:14,860 --> 00:05:15,880
is of size and cross.

76
00:05:15,880 --> 00:05:26,650
And so I need to create one visitor that he throws and and we need to initialize this area by a false.

77
00:05:28,650 --> 00:05:37,380
So what am doing here, this is our grid, I am creating one visitor to L.A. and initially all the value

78
00:05:37,380 --> 00:05:38,150
will be false.

79
00:05:38,790 --> 00:05:40,320
No element is visited.

80
00:05:40,340 --> 00:05:42,660
So a false, false, false, right.

81
00:05:42,990 --> 00:05:46,230
False here, Voltaire, false, false, false and false.

82
00:05:46,560 --> 00:05:48,360
So this is the syntax for doing that.

83
00:05:49,290 --> 00:05:49,830
Simple.

84
00:05:50,220 --> 00:05:54,270
Now what we'll do, we will push this starting vertex in our queue.

85
00:05:55,740 --> 00:05:59,420
So we need to push the starting vertex in our queue.

86
00:05:59,430 --> 00:06:03,990
So first of all, we need to create queue of integers.

87
00:06:04,470 --> 00:06:07,730
You and we need to push the starting.

88
00:06:10,260 --> 00:06:13,700
We need to push the starting vertex, the source vertex.

89
00:06:14,460 --> 00:06:19,650
So sorry, this will be queue of cell rate.

90
00:06:19,830 --> 00:06:21,840
You will contain one cell.

91
00:06:22,800 --> 00:06:24,190
You will contain one cell.

92
00:06:24,210 --> 00:06:25,780
So that will be key off cell.

93
00:06:26,550 --> 00:06:27,480
So first cell.

94
00:06:27,480 --> 00:06:28,640
What is the expert in it?

95
00:06:28,680 --> 00:06:29,100
Zero.

96
00:06:29,460 --> 00:06:31,170
What is the Y coordinate zero.

97
00:06:31,170 --> 00:06:32,960
And what is the distance distances.

98
00:06:32,970 --> 00:06:33,240
One.

99
00:06:37,300 --> 00:06:46,300
Right distances when so I have discussed this is one cell queue will contain one cell and for this cell,

100
00:06:46,300 --> 00:06:51,220
what is the extraordinary digital what is the record and zero and what is the distance distances when

101
00:06:52,480 --> 00:06:53,410
it is containing?

102
00:06:53,710 --> 00:06:55,140
I am encountering one zero.

103
00:06:55,150 --> 00:06:55,590
That's right.

104
00:06:55,660 --> 00:06:55,960
When.

105
00:06:56,350 --> 00:06:56,770
Right.

106
00:06:57,670 --> 00:07:04,710
So since I have visited this vortex, that is I have pushed this vertex in the queue.

107
00:07:04,720 --> 00:07:09,190
So what I will do, I will mark this as visitor that I have visited.

108
00:07:09,190 --> 00:07:13,840
This so visited of 090 zero is proof.

109
00:07:14,500 --> 00:07:18,130
I have visited the source cell source vertex.

110
00:07:18,610 --> 00:07:19,030
Right.

111
00:07:19,660 --> 00:07:21,430
And now what do we have?

112
00:07:22,510 --> 00:07:24,760
We will have the standard loop, right.

113
00:07:25,000 --> 00:07:31,410
While the queue is not empty, while the queue is not empty.

114
00:07:31,930 --> 00:07:36,610
So what we are going to do is let's pop one cell therapy or temp.

115
00:07:37,300 --> 00:07:39,700
So cell temp is basically called out front.

116
00:07:40,840 --> 00:07:45,460
And then what we are going to do is dude artpop simple.

117
00:07:45,700 --> 00:07:46,930
So let's check here.

118
00:07:47,050 --> 00:07:55,990
So if the content of this cell is equal to and minus one and the Y coordinate of this cell is equal

119
00:07:56,110 --> 00:08:00,770
to and minus one, that is I have reached the last cell.

120
00:08:01,030 --> 00:08:07,330
So if I have reached the last cell, I am going to return that distance for this sorted out distance

121
00:08:07,840 --> 00:08:08,180
rate.

122
00:08:08,350 --> 00:08:13,190
So what I am doing here is I am checking the X coordinate of the cell and by coordinating the cell.

123
00:08:13,420 --> 00:08:18,640
So if the X coordinator of the cell and via coordinate of the cell is corresponding to this box, then

124
00:08:18,640 --> 00:08:24,470
what I need to do, I just need to return the value so I am returning the value I'm returning for.

125
00:08:24,880 --> 00:08:25,230
Right.

126
00:08:25,600 --> 00:08:34,510
So if this is not the case, if this is not the case, if I am not standing at the last cell, then

127
00:08:34,780 --> 00:08:42,400
from the given cell, I can move in either directions so I can move in either direction.

128
00:08:42,400 --> 00:08:50,450
So I equals zero i.e. less then eight I plus plus I can move in a direction.

129
00:08:50,470 --> 00:08:52,420
So what will be the new X coordinate.

130
00:08:52,780 --> 00:08:59,770
New X coordinate will be the original X coordinate plus the change in X direction.

131
00:09:03,150 --> 00:09:13,530
Similarly, what will be the Y coordinate, so y coordinate will be the original Y coordinate the cell

132
00:09:13,530 --> 00:09:18,020
where I'm am standing, let's the change in y coordinate.

133
00:09:19,800 --> 00:09:20,170
Right.

134
00:09:20,420 --> 00:09:23,090
So this is so what I'm doing here.

135
00:09:24,450 --> 00:09:25,760
I'm standing at this and.

136
00:09:25,770 --> 00:09:26,160
Right.

137
00:09:27,900 --> 00:09:29,660
I am standing at this cell.

138
00:09:29,670 --> 00:09:34,950
So this is the X Guardian in the Y coordinate so I can move in either direction from this cell.

139
00:09:35,340 --> 00:09:35,760
Right.

140
00:09:35,760 --> 00:09:37,050
I can move in each direction.

141
00:09:37,320 --> 00:09:42,730
So what I'm doing, I'm calculating the new one, basically the new X and Y coordinate.

142
00:09:42,750 --> 00:09:51,720
So from this cell, the original X coordinate plus the change in each direction, similarly the change

143
00:09:51,720 --> 00:09:56,180
in direction, similarly the change in direction, the change in direction.

144
00:09:56,340 --> 00:09:57,750
So that is what I am doing.

145
00:09:58,050 --> 00:09:58,410
Right.

146
00:09:58,440 --> 00:10:05,760
I am finding out the new X and Y coordinate, so I am finding out the new X and Y coordinate and what

147
00:10:05,760 --> 00:10:13,800
I will do, I will push this new X and Y coordinate into the Q So what is the new X according that this

148
00:10:13,800 --> 00:10:18,060
is X and Y and what is the distance distances.

149
00:10:18,270 --> 00:10:21,240
The dart distance plus one.

150
00:10:25,700 --> 00:10:27,000
See what I'm doing here?

151
00:10:29,480 --> 00:10:34,460
I told you so for this, the distance is one for the distances too.

152
00:10:34,700 --> 00:10:35,720
So I'm standing here.

153
00:10:36,500 --> 00:10:40,170
If I will go ahead, but I will do I will increase the distance by one.

154
00:10:40,190 --> 00:10:41,990
I will do distance plus plus rate.

155
00:10:42,110 --> 00:10:45,260
So I'm increasing the distance, my distance plus one.

156
00:10:46,400 --> 00:10:46,820
Right.

157
00:10:47,390 --> 00:10:49,910
So we cannot directly do this.

158
00:10:49,910 --> 00:10:55,640
Right, because first we need to check whether X is a valid coordinate or not vice valid coordinate

159
00:10:55,640 --> 00:10:56,130
or not.

160
00:10:56,900 --> 00:11:00,440
Similarly, X and Y should contain zero right in our kill.

161
00:11:00,620 --> 00:11:05,720
Our cue will only contain zero hour will not contain one because we are only interested in.

162
00:11:06,080 --> 00:11:11,210
So we need to find out the shortest path and I can only move along as it was not once before.

163
00:11:11,210 --> 00:11:17,390
Doing this, I need to write few if condition that we need to check the validity with X and Y is a valid

164
00:11:17,390 --> 00:11:18,230
coordinate or not.

165
00:11:18,710 --> 00:11:23,020
So for checking the validity, what are the conditions that we need to write to?

166
00:11:23,030 --> 00:11:27,800
First of all, X must be good in order close to zero then only it is a valid coordinate.

167
00:11:27,800 --> 00:11:28,160
Right.

168
00:11:28,790 --> 00:11:32,020
And X must be less than ten then.

169
00:11:32,090 --> 00:11:33,380
Then it is a valid coordinate.

170
00:11:33,910 --> 00:11:39,400
Similarly, V must be greater than or equal to zero and Y must be less than.

171
00:11:39,410 --> 00:11:40,940
And and.

172
00:11:41,840 --> 00:11:50,120
We need to check whether this X coordinate and Y coordinate is containing one or zero, so it must contain

173
00:11:50,120 --> 00:11:52,760
zero that we will only move along zero.

174
00:11:53,120 --> 00:11:54,780
So it must contain zero.

175
00:11:55,400 --> 00:11:58,880
And this cell must not be visited.

176
00:12:00,030 --> 00:12:00,240
Right.

177
00:12:00,410 --> 00:12:02,510
That's why we have it ready.

178
00:12:02,900 --> 00:12:06,620
So this cell that is X coordinate and why coordinate.

179
00:12:06,620 --> 00:12:09,860
So this cell must not be visited before then.

180
00:12:09,860 --> 00:12:11,240
Only I will visit this.

181
00:12:14,860 --> 00:12:22,420
So I will visit this, and since I have pushed this into our queue, what I need to do, I need to mark

182
00:12:22,420 --> 00:12:23,310
this as a visitor.

183
00:12:23,340 --> 00:12:25,990
I need to mark this cell as visited.

184
00:12:26,350 --> 00:12:30,610
So visitors of x ray is a close to two.

185
00:12:33,190 --> 00:12:33,580
Right.

186
00:12:34,690 --> 00:12:37,300
And that that will be the complete code.

187
00:12:37,690 --> 00:12:43,300
And finally, what you are going to do is when your kid will become empty and you are not able to reach

188
00:12:43,300 --> 00:12:45,820
the last index, so you will return minus one.

189
00:12:46,570 --> 00:12:46,980
Right.

190
00:12:47,230 --> 00:12:49,630
So we are returning our answer here.

191
00:12:49,630 --> 00:12:54,820
But if we are not able to reach the last index, then our answer will be minus one.

192
00:12:56,530 --> 00:12:57,010
Right.

193
00:12:59,010 --> 00:13:00,540
So that is the complete goal.

194
00:13:01,110 --> 00:13:06,570
One more thing, let's check a few basic conditions here before we are writing our code.

195
00:13:06,870 --> 00:13:15,690
So basic condition is if the first cell of the Matrix, if the first cell of the graph is containing

196
00:13:15,690 --> 00:13:19,380
one, that means there will be no answer.

197
00:13:19,890 --> 00:13:22,140
Right, if the first box is containing one.

198
00:13:23,610 --> 00:13:29,280
So if this first box, instead of containing zero, if the first box is containing one, then the third,

199
00:13:29,490 --> 00:13:31,890
you will directly return, minus one you cannot reach here.

200
00:13:32,310 --> 00:13:36,050
So if the first is containing one, then done minus one that.

201
00:13:38,100 --> 00:13:40,910
So that will be the code for solving this problem.

202
00:13:40,920 --> 00:13:42,260
So let's see.

203
00:13:42,270 --> 00:13:47,460
Let's try to run our code and let's see whether our code is correct or not or it has some bugs.

204
00:13:50,730 --> 00:13:54,930
So here, yep, and I need to write semicolon.

205
00:14:02,000 --> 00:14:04,130
Yep, so let's try to sum our gold.

206
00:14:07,960 --> 00:14:12,780
Yeah, so basically, our court is working fine, right?

207
00:14:13,240 --> 00:14:19,900
So that will be the complete code and let us discuss the time and the space complexity.

208
00:14:21,850 --> 00:14:25,240
So complexity is very obvious.

209
00:14:25,540 --> 00:14:29,520
You are creating one visitor at a rate of size and gross.

210
00:14:29,520 --> 00:14:34,210
And so this will be the time, complexity, sorry, space, complexity, big off and square.

211
00:14:35,230 --> 00:14:37,650
Now, let's talk about the time complexity.

212
00:14:37,990 --> 00:14:46,360
So in time, complexity, what we are doing, so we are trading or work to date, we are trading overkill.

213
00:14:46,750 --> 00:14:50,740
So in the worst case, how many elements of representing you?

214
00:14:51,340 --> 00:14:58,990
So if my matrix is containing zeros, all zeros, so time complexity will be we will go through each

215
00:14:58,990 --> 00:15:02,500
and every element once the time complexity is big off and square.

216
00:15:02,530 --> 00:15:05,970
So this is the time and the space complexity for this problem.

217
00:15:06,280 --> 00:15:06,730
Right.

218
00:15:07,420 --> 00:15:13,610
And this is the entire code, very simple write simple BFW algorithm.

219
00:15:14,710 --> 00:15:16,920
So this is all about this device.

220
00:15:16,930 --> 00:15:20,790
If you have any doubt in this problem to ask me, I will see you in the next one.

221
00:15:20,800 --> 00:15:21,400
Thank you.

