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.

