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.