1 00:00:00,840 --> 00:00:03,000 Hi, everyone, welcome to this new video. 2 00:00:03,030 --> 00:00:07,860 So in this video, we are going to solve this question shortest path in a binary matrix. 3 00:00:08,460 --> 00:00:12,150 So we are given a binary matrix that means zeros and ones. 4 00:00:12,420 --> 00:00:16,290 So if this is my matrix, it will contain zeros and ones. 5 00:00:16,790 --> 00:00:25,010 I am standing at the first box and I want to reach the last box and I need to return this shortest path. 6 00:00:25,140 --> 00:00:30,450 But there is one condition and the condition is basically since the binary matrix, it will contain 7 00:00:30,450 --> 00:00:31,320 zeros and ones. 8 00:00:31,320 --> 00:00:38,160 You can only move two zeros, we can only move two zeros and we cannot move to one. 9 00:00:38,580 --> 00:00:38,900 Right. 10 00:00:39,300 --> 00:00:40,420 So that is the condition. 11 00:00:40,890 --> 00:00:49,260 So all the cells of the part must contain zero and you can move in each direction from a given box. 12 00:00:49,650 --> 00:00:50,090 Right. 13 00:00:50,310 --> 00:00:53,700 So from a given box, we can move in either directions. 14 00:00:57,640 --> 00:01:04,030 Right, and we need to find out the length of a clear path, a clear path means the path in which you 15 00:01:04,030 --> 00:01:06,970 have Xeros only zeros and not ones. 16 00:01:07,720 --> 00:01:10,660 So let's take a few example and let's try to understand. 17 00:01:12,010 --> 00:01:15,390 So let's talk about the first example which is given in the question. 18 00:01:16,690 --> 00:01:21,130 So here it is very clear that the answer will be too late. 19 00:01:21,280 --> 00:01:24,200 It will start us standing here and you want to reach here. 20 00:01:24,370 --> 00:01:26,020 So how many zeros you visited? 21 00:01:26,320 --> 00:01:28,270 You visited toolbox, right? 22 00:01:28,300 --> 00:01:28,700 That's right. 23 00:01:28,720 --> 00:01:30,100 The output is two. 24 00:01:31,120 --> 00:01:36,000 So if we visualize this matrix as a graph, then how will the graph look like? 25 00:01:36,280 --> 00:01:44,010 So let's name these nodes A, B, C and B, so I have this node A and it is containing zero. 26 00:01:44,050 --> 00:01:53,710 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 27 00:01:53,710 --> 00:01:57,550 one and I can go to the which is containing zero. 28 00:01:57,850 --> 00:02:03,310 And obviously from C I can go to eight also from B I can go to able to from the. 29 00:02:03,310 --> 00:02:04,230 I can go to to. 30 00:02:04,740 --> 00:02:07,460 So that's why these will be by-election. 31 00:02:07,480 --> 00:02:10,960 And so I am visualizing Matrix as a graph. 32 00:02:11,620 --> 00:02:11,920 Right. 33 00:02:12,310 --> 00:02:16,140 So in this graph this is my graph. 34 00:02:16,660 --> 00:02:20,290 And what is the longest. 35 00:02:20,290 --> 00:02:20,580 Sorry. 36 00:02:20,590 --> 00:02:22,030 What is the shortest part. 37 00:02:22,570 --> 00:02:24,040 The shortest battle with this one. 38 00:02:24,040 --> 00:02:24,440 Right. 39 00:02:24,460 --> 00:02:25,840 I'm talking about the spot. 40 00:02:26,140 --> 00:02:27,670 So how many zeros I visited. 41 00:02:27,670 --> 00:02:29,060 I visited two zeros. 42 00:02:29,080 --> 00:02:30,280 So the output is two. 43 00:02:31,750 --> 00:02:35,140 So can we solve this question using best algorithm? 44 00:02:35,320 --> 00:02:35,980 Yes. 45 00:02:36,720 --> 00:02:41,240 B, if this algorithm is used to find out the shortest path in a graph. 46 00:02:42,820 --> 00:02:46,890 So basically, Vadum is used to find out shortest path in a graph. 47 00:02:46,900 --> 00:02:50,560 And here in this question, we need to find the shortest path. 48 00:02:50,830 --> 00:02:54,310 So BFC algorithm is the perfect algorithm for solving this problem. 49 00:02:54,700 --> 00:02:56,170 Let's take one more example. 50 00:02:56,500 --> 00:02:58,900 Let's try to see one more example and let's see. 51 00:03:00,370 --> 00:03:03,940 So here in this example, I can see. 52 00:03:04,660 --> 00:03:10,680 So from here I am going at this box now from this box, I had two options. 53 00:03:10,720 --> 00:03:15,430 I can go here as well as here, but we need to find out the shortest path that. 54 00:03:15,430 --> 00:03:18,010 So I will come here and then from this I will come here. 55 00:03:18,250 --> 00:03:22,250 So how many zeros I visited for zeros that tied the output is four. 56 00:03:22,270 --> 00:03:29,020 For in this case, the first box is basically one, right, one zero zero. 57 00:03:29,020 --> 00:03:31,480 Then I have one one zero, then one one zero. 58 00:03:31,690 --> 00:03:33,610 So the first box is containing one. 59 00:03:33,820 --> 00:03:34,810 It should be zero. 60 00:03:35,110 --> 00:03:35,480 Right? 61 00:03:35,560 --> 00:03:37,600 So that's why the output is minus one. 62 00:03:37,610 --> 00:03:40,780 I cannot move to the box, which is containing one. 63 00:03:41,020 --> 00:03:43,090 So in this case, there is no short list. 64 00:03:43,090 --> 00:03:44,380 But so that time minus one. 65 00:03:44,680 --> 00:03:47,900 So here in this example, let's see how the algorithm will help us. 66 00:03:48,160 --> 00:03:49,800 So I told you what we need to do. 67 00:03:49,810 --> 00:03:54,580 We need to visualize grid as our we need to visualize Matrix as a graph. 68 00:03:55,300 --> 00:03:56,680 So this is ABC. 69 00:03:58,120 --> 00:03:59,920 The F and G. 70 00:04:01,300 --> 00:04:08,260 So let's talk about Nordea, this is our Nordea, so from not a I can move to not be, which is containing 71 00:04:08,260 --> 00:04:10,480 zero, so not is also containing zero. 72 00:04:11,640 --> 00:04:17,769 I can move to Nordea, which is containing one, and I can move the node, which is also containing 73 00:04:17,769 --> 00:04:18,019 one. 74 00:04:18,370 --> 00:04:22,210 So similarly, these are bidirectional edges. 75 00:04:24,230 --> 00:04:24,680 Right. 76 00:04:24,970 --> 00:04:26,790 So now let's talk about this node. 77 00:04:27,580 --> 00:04:30,790 So from B I can go to see which is correct. 78 00:04:31,270 --> 00:04:39,760 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 79 00:04:39,760 --> 00:04:41,550 also go to E and vice versa. 80 00:04:42,400 --> 00:04:45,320 I can go to E and vice versa. 81 00:04:46,360 --> 00:04:48,520 So yep. 82 00:04:48,790 --> 00:04:56,230 Now from B I can also go to F, I can also go to F which is containing zero. 83 00:04:58,850 --> 00:05:03,570 Right now, let's talk about a half hour. 84 00:05:03,690 --> 00:05:14,750 First, let's talk about C. So from C. I can go to F, I can go to B, I can go to E. 85 00:05:18,530 --> 00:05:30,920 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, 86 00:05:31,070 --> 00:05:34,880 I, and so I can go to IHI, which is containing Xeros. 87 00:05:37,700 --> 00:05:43,910 And many of the notes, right, and the rest of the graph, we are only interested in the truth, so 88 00:05:43,910 --> 00:05:44,970 I'm not considering one. 89 00:05:45,650 --> 00:05:53,210 So this is our graph and we want to find out the shortest part starting from this node. 90 00:05:54,020 --> 00:05:55,550 And I want to reach this node. 91 00:05:55,550 --> 00:05:55,870 Right. 92 00:05:55,910 --> 00:05:56,760 This is the last one. 93 00:05:56,780 --> 00:05:57,200 All right. 94 00:05:57,980 --> 00:05:59,200 I want to reach this node. 95 00:05:59,780 --> 00:06:02,180 So which algorithm can help us here? 96 00:06:02,180 --> 00:06:07,250 Best algorithm, because BFW algorithm is used to find out the shortest path in a graph. 97 00:06:07,670 --> 00:06:14,900 Beerfest algorithm is nothing but the level that I drivers in the laboratory that we used to do in trees. 98 00:06:14,930 --> 00:06:17,300 So Beerfest is nothing, just the louder traversal. 99 00:06:17,510 --> 00:06:19,140 So this is your first level. 100 00:06:19,520 --> 00:06:20,910 This is your second level. 101 00:06:21,260 --> 00:06:22,630 This is your third level. 102 00:06:22,760 --> 00:06:24,710 And this is your fourth level. 103 00:06:24,950 --> 00:06:26,330 Since this is the fourth level. 104 00:06:26,350 --> 00:06:27,650 That's why the output is four. 105 00:06:29,090 --> 00:06:29,510 Right. 106 00:06:29,750 --> 00:06:35,930 So BFW algorithm is the perfect algorithm for solving this problem, for finding out the shortest path. 107 00:06:36,650 --> 00:06:41,690 So whenever you encounter one problem and that problem is asking you to find out the shortest part, 108 00:06:42,050 --> 00:06:43,250 there are two directions. 109 00:06:43,370 --> 00:06:45,080 First one is using the grid approach. 110 00:06:45,470 --> 00:06:46,710 Grid approach will not work. 111 00:06:47,300 --> 00:06:51,830 Second approach you can think of finding the shortest path is using dynamic programming that also will 112 00:06:51,830 --> 00:06:52,540 not work here. 113 00:06:52,730 --> 00:06:58,210 And the third option, so you can think of BFX whether BFW will work or not. 114 00:06:58,250 --> 00:07:00,440 So BFW will work in this problem. 115 00:07:02,120 --> 00:07:02,560 Right. 116 00:07:02,870 --> 00:07:07,330 So in NextRadio, what I'm going to do is I'm going to write the code for the BFC algorithm. 117 00:07:07,730 --> 00:07:11,960 So I highly recommend that before watching the next video, you should try to write the code for this 118 00:07:11,960 --> 00:07:12,830 problem yourself. 119 00:07:13,790 --> 00:07:14,090 Right. 120 00:07:14,380 --> 00:07:17,190 And obviously in the next video, you can see my solution. 121 00:07:18,020 --> 00:07:20,660 So that is a device that is all about this video. 122 00:07:20,670 --> 00:07:21,980 I will see you in the next one. 123 00:07:22,160 --> 00:07:22,760 Thank you.