1
00:00:01,380 --> 00:00:03,750
Hi, everyone, welcome to this new video.

2
00:00:03,780 --> 00:00:08,840
So in this video, we are going to discuss about this question night on a chessboard.

3
00:00:10,080 --> 00:00:15,090
So we have this night and this night can move in each direction.

4
00:00:15,300 --> 00:00:19,860
So these are the total eight directions possible in which the knight can move.

5
00:00:19,860 --> 00:00:20,250
Right.

6
00:00:20,430 --> 00:00:25,980
So Knight can move in total eight directions from a given box, from a given cell.

7
00:00:27,720 --> 00:00:32,810
Now, given this chess board, so a normal chess board is of size across it.

8
00:00:33,030 --> 00:00:38,860
But in this problem, it is given that the dimension of the chess board will be given to us and they

9
00:00:38,880 --> 00:00:42,240
do, the damage of the chess board will be given to us as input.

10
00:00:42,450 --> 00:00:44,550
So we cannot assume it is a closet.

11
00:00:45,360 --> 00:00:48,150
OK, so given this source point.

12
00:00:50,060 --> 00:00:54,740
So this whole point can be any point in the chessboard, it can be this, it can be this.

13
00:00:55,070 --> 00:00:56,540
It can be this.

14
00:00:56,540 --> 00:00:57,430
It can be this.

15
00:00:57,440 --> 00:00:59,660
So any point can be the source point.

16
00:01:00,170 --> 00:01:02,870
And we are also given the destination point.

17
00:01:03,350 --> 00:01:03,620
Right.

18
00:01:03,890 --> 00:01:05,660
So we are given any source point.

19
00:01:05,660 --> 00:01:09,140
Let's say this is the whole point and this is the destination point.

20
00:01:09,620 --> 00:01:10,010
Right.

21
00:01:10,160 --> 00:01:13,270
So so this point means your night is presented.

22
00:01:14,060 --> 00:01:19,790
That is the meaning of swords point, the position, the point at which your knight is standing.

23
00:01:19,790 --> 00:01:20,180
Right.

24
00:01:20,480 --> 00:01:28,040
And we need to tell whether the knight can move to a destination or not, whether Knight can move to

25
00:01:28,040 --> 00:01:35,120
the destination point or not, if it is able to move to the destination point, then you need to return

26
00:01:35,120 --> 00:01:36,560
the minimum number of moves.

27
00:01:37,100 --> 00:01:43,070
You need to return a minimum number of moves in which Knight will be able to reach the destination point

28
00:01:43,070 --> 00:01:44,210
from this source point.

29
00:01:45,640 --> 00:01:46,070
Right.

30
00:01:46,300 --> 00:01:54,720
So one example is given to us here, and this is the example, right?

31
00:01:54,910 --> 00:02:00,460
So in this example, it is given that the dimension of the chessboard are eight.

32
00:02:00,460 --> 00:02:01,810
Crossett So.

33
00:02:01,810 --> 00:02:04,450
McCrossin So the dimension of chessboard is it?

34
00:02:04,450 --> 00:02:07,680
CROSSETT The starting point is one and one.

35
00:02:07,990 --> 00:02:09,970
So one and one is this whole point.

36
00:02:10,210 --> 00:02:16,200
Your night is present at this position and this is the destination point.

37
00:02:16,390 --> 00:02:17,860
So you want to reach here.

38
00:02:19,890 --> 00:02:21,720
This is the destination point.

39
00:02:22,890 --> 00:02:26,600
This is your source point, this is his point.

40
00:02:26,610 --> 00:02:27,770
This is an point.

41
00:02:27,780 --> 00:02:35,130
Your night is present at this point and you need to return in minimum number of moves.

42
00:02:35,130 --> 00:02:37,050
You will be able to reach their destination.

43
00:02:37,080 --> 00:02:39,150
So it is saying in six moves.

44
00:02:39,390 --> 00:02:40,490
In six moves.

45
00:02:40,500 --> 00:02:42,420
So six is the minimum number of moves.

46
00:02:42,750 --> 00:02:46,260
Remember, these are the minimum number of moves required.

47
00:02:46,470 --> 00:02:52,500
So in six moves, Knight will be able to move to the destination and it will be able to reach the destination

48
00:02:52,500 --> 00:02:52,850
point.

49
00:02:53,040 --> 00:02:58,260
And if you are not able to reach their destination point, then in that case you need to return minus

50
00:02:58,260 --> 00:02:58,500
one.

51
00:02:58,620 --> 00:03:02,400
And if you are able to reach, then you need to return the minimum number of moves.

52
00:03:02,770 --> 00:03:03,140
Right.

53
00:03:03,270 --> 00:03:04,910
So this is the problem statement.

54
00:03:05,130 --> 00:03:07,110
I hope you have understood the problem statement.

55
00:03:07,320 --> 00:03:08,610
So again, what is this?

56
00:03:09,120 --> 00:03:09,860
What we need to do?

57
00:03:09,870 --> 00:03:11,850
We need to find out the shortest path.

58
00:03:12,300 --> 00:03:13,880
What is the given input?

59
00:03:13,890 --> 00:03:15,720
So given input is the grid.

60
00:03:15,720 --> 00:03:16,820
That is a graph.

61
00:03:17,070 --> 00:03:18,870
So given input is a graph.

62
00:03:19,830 --> 00:03:20,270
Right.

63
00:03:20,280 --> 00:03:27,510
We can visualize the given board as graph and virtually the nodes nodes will be this will be one node,

64
00:03:27,510 --> 00:03:28,750
this will be another node.

65
00:03:28,770 --> 00:03:33,000
Similarly, we will have nodes in between right where the knights can move.

66
00:03:33,690 --> 00:03:39,120
So we can visualize this problem as a graph and we need to find out the shortest path and for finding

67
00:03:39,120 --> 00:03:39,810
out the shortest.

68
00:03:39,810 --> 00:03:43,910
But we use BFW algorithm, right?

69
00:03:44,310 --> 00:03:48,320
So this problem is nothing but just the variation of BFX.

70
00:03:50,130 --> 00:03:55,070
So you need to write the code for Beerfest problem for finding out minimum number of moves.

71
00:03:55,500 --> 00:03:58,720
So we have already a very similar problem in our last video.

72
00:03:58,740 --> 00:04:01,800
So this was the problem, shortest button by animatics.

73
00:04:01,950 --> 00:04:06,030
So in this problem also for finding out the shortest path, we use the best algorithm.

74
00:04:06,210 --> 00:04:13,530
So we're going to do just copy the entire code and paste the entire code here and just do the modification

75
00:04:13,530 --> 00:04:15,240
according to the U.N. problem statement.

76
00:04:15,240 --> 00:04:15,920
And that's it.

77
00:04:16,350 --> 00:04:16,660
Right.

78
00:04:16,890 --> 00:04:18,779
So you need to do a few modifications.

79
00:04:19,050 --> 00:04:19,500
Right.

80
00:04:19,680 --> 00:04:25,110
So what few modifications can be so the few modifications can be a member.

81
00:04:25,140 --> 00:04:29,510
We created the area and divided the change in the right direction.

82
00:04:29,730 --> 00:04:32,700
So obviously this will change according to the night's move.

83
00:04:32,910 --> 00:04:33,390
Right.

84
00:04:33,670 --> 00:04:38,580
So night night used to move in two point five moves late.

85
00:04:39,340 --> 00:04:44,730
So you need to change the X and you need to change it by changing direction, changing direction.

86
00:04:45,120 --> 00:04:46,440
What else do you need to change?

87
00:04:46,590 --> 00:04:51,570
So here the grid is basically one indexed, based and not zero indexed based.

88
00:04:51,810 --> 00:04:55,690
So you need to check you need to modify the code according to that rate.

89
00:04:55,890 --> 00:05:03,430
So the end point is eight compute rate and the chessboard is a size eight crossette.

90
00:05:03,720 --> 00:05:08,240
So here we can identify the indexing is one index based and not zero indexing.

91
00:05:08,520 --> 00:05:10,860
So you need to do some modification according to that.

92
00:05:11,490 --> 00:05:17,190
So there will be few modifications that you need to do in the previous code and that code will work

93
00:05:17,190 --> 00:05:18,410
absolutely fine here.

94
00:05:18,540 --> 00:05:24,690
So I highly recommend that you try modifying the existing code and if you are able to do that, then

95
00:05:24,690 --> 00:05:25,320
it's very good.

96
00:05:25,350 --> 00:05:32,400
So ideally, you should be able to convert this code easily into the into the current problem code.

97
00:05:32,670 --> 00:05:33,720
Now, you don't just build.

98
00:05:33,960 --> 00:05:34,340
Right?

99
00:05:34,350 --> 00:05:39,390
So I will be writing the code and I will be doing modifications in this code in front of you in the

100
00:05:39,390 --> 00:05:40,020
next room.

101
00:05:40,020 --> 00:05:42,520
But I highly recommend that you must give it a try.

102
00:05:42,540 --> 00:05:42,880
Right.

103
00:05:42,900 --> 00:05:44,700
So this is all about this device.

104
00:05:44,940 --> 00:05:47,340
In next, we will be writing the code for this problem.

105
00:05:48,570 --> 00:05:49,930
I will see you in the next one.

106
00:05:50,220 --> 00:05:50,700
Thank you.