Rat in a maze | Part 1 | Recursion & Backtracking | DSA by Nishant Chahar | Codes available
Rat in a maze | Part 1 | Recursion & Backtracking | DSA by Nishant Chahar | Codes available
Here in this video, we are going to see the approach for our 3rd backtracking problem Rat in a maze. Make sure that you watch the previous lecture where we discussed the approach to solve this problem .
Previous lecture : • Code for N-Queens problem | Part 2 | …
Problem: https://practice.geeksforgeeks.org/pr…
You can use my code NISHANT to get 15% Off on all GFG courses.
✨ Important Links ✨
- Don’t Click Here: https://bit.ly/3afmPha
- Telegram Link: https://t.me/codeIn10byNishant
- Github Repo Link: https://github.com/chaharnishant11/Co…
✨ Hashtags ✨
#NishantChahar #Microsoft #DSA #Recursion #FAANG #NSIT #NSUT #engineering #internship #college
✨tags ✨
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn Operating systems
where to learn dbms
where to learn oops
where to learn computer networks
where to learn low level design
where to learn cs fundamentals
Sanchit jain
Gaurav sen
Gate smashers
Placement guide
How to start programming
where to learn cpp
where to learn python
where to learn javascript
where to learn java
Placement guide
Nishant Chahar Placement Guide
languages to learn
resources to learn data structures
Projects development
AR/VR
Blockchain Machine learning
Deep Learning
Software developer engineer ,
Side projects ,
Importance of side projects ,
Machine Learning Engineer,
How to become a machine learning engineer ,
Associate engineer
Data structures Algorithms
College Life, College, Memories
Fun Fests Chill Enjoy
IITD Mood indigo rendezvous IIT
NSUT Moksha DTU Engifest
Bits Bitsgoa
Namaste Javascript
Namaste Javascript Akshay Saini
Apna college
Apna college c++
apna college DSA
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn programming
how to start coding
where to learn coding
where to learn DSA
resources to learn programming
how to crack amazon
how to crack placement
blockchain
what is blockchain
blockchain technology
blockchain technology explained
blockchain explained
blockchain technology in hindi
web development roadmap
roadmap to learn web development
android development roadmap
MERN stack roadmap
machine learning roadmap
roadmap to learn machine learning
roadmap for deep learning
roadmap for 2nd years
roadmap for opensource
roadmap for ios development
roadmap for deep learning
roadmap to learn DSA
Content
0 -> Hi guys welcome to the channel code in 10. I am Nishant Chahar
2.579 -> So in today's video, we gonna talk about this problem
4.944 -> That you can read. Its name is a rat in a maze
7.825 -> This is a problem of backtracking
9.704 -> This is also a problem with graph
11.029 -> Okay
11.752 -> so we will be doing this in the graph also
13.137 -> Currently we are studying it is backtracking
14.778 -> So what is the scene in it
16.468 -> There is a rat
17.547 -> Okay
18.11 -> it enters from a corner
19.694 -> and it has to reach the other corner
21.796 -> Okay
22.562 -> Now he has multiple ways of reaching till other corner
26.139 -> But there is one condition
28.657 -> That at the places where there is 1
30.471 -> in this matrix, a 2D matrix is given
32.834 -> It can go through that way only
35.288 -> in the places where there is 0, there is a wall
37.162 -> And where it is 1, there is no wall there
38.78 -> So we have to tell how many multiple paths does it has
42.632 -> So what we do
43.672 -> Lets take this example
45.55 -> and lets try to solve
47.357 -> So we are given this matrix
50.275 -> Okay
52.217 -> what is the matrix? It is a 2D array
54.364 -> 2 Dimensional array
56.835 -> So we are given this matrix
61.312 -> Now we are saying in this matrix
63.819 -> This is 0, this is 1, this is 2, this is 3
66.331 -> This is 0, this is 1
67.997 -> This is 2, this is 3
69.431 -> so this is your 4 x 4 matrix
72.125 -> This is your 4 x 4 matrix
73.874 -> what you are told in it? This 3, 3, we have to reach this position
79.543 -> by starting from 0,0
80.937 -> This is our problem statement
83.099 -> We are told only this thing in it
84.277 -> That at the places where there is one
85.822 -> Rat can go only by following that path
89.003 -> till last
89.983 -> There is one more thing in it
91.145 -> that the rat can move in all 4 directions
93.472 -> it can go up as well as down
96.473 -> It can go right and left as well
102.188 -> Okay
104.081 -> It is simple
105.923 -> And what we have to tell? we have to tell its path
107.877 -> All the paths that are possible
110.024 -> We have to return all the possible paths
114.18 -> Now how we will get to know that this is a problem of backtracking
118.802 -> You are given here clearly
121.417 -> That tell all the possible paths
123.136 -> when we say all possible like this
125.975 -> Okay
126.662 -> that return everything
128.536 -> So we have to apply recursion and backtracking
130.955 -> There is one more thing in it
131.854 -> In path no cell can be visited more than once
134.557 -> If the source cell is 0
136.392 -> The rat cannot move
137.256 -> to any other cell
138.83 -> what does it means
140.163 -> if the 0 is placed at 0,0
143.718 -> Means if there is wall in starting
145.714 -> Okay
147.237 -> If there is wall in starting
148.226 -> How will the rat enter in the maze
149.832 -> So we just have to return the empty array
153.368 -> In which there will be no string
154.709 -> Empty
156.187 -> Okay
157.784 -> The second condition is this
159.604 -> you cannot visit the second cell twice
162.299 -> you cannot visit that twice
165.932 -> so 2 visits are not allowed
167.485 -> So now what we will do to ensure this thing
169.816 -> we will make a 2D index
171.41 -> we call it visited matrix
174.742 -> So when we will be doing graphs
177.826 -> so we will use this a lot of times
180.126 -> 2D visited matrix, 2D visited array
182.378 -> Okay
183.144 -> We will use this a lot
184.646 -> But currently, we are using this visit for this problem
188.134 -> Because we are told here that we cannot go with a cell twice
190.973 -> So what we will do to ensure this thing
193.589 -> 2D matrix will work like visited matrix
196.277 -> It will tell us that if we have come to this cell before or not
199.247 -> Okay
200.351 -> So we have to do nothing
201.333 -> there will be 4 calls
202.714 -> That we apply in everything always
205.864 -> are there 4 possible ways?
207.371 -> The recursion and backtracking that we are doing from past so many days
209.401 -> What we do in that. we apply call in all the possible paths
214.493 -> Okay
215.129 -> What we have to do? We have to check on our current position
218.274 -> That is there 0 on current position
220.607 -> Or is there 1 on current position
222.074 -> is it visited or not
223.469 -> if we have done our work
225.444 -> Recursion will do all the other work
227.526 -> We call it recursive leap of faith
229.577 -> We have read many times
230.533 -> Okay
231.128 -> We just have to do our step
232.43 -> We just have to do step calculation
233.579 -> Recursion will bring all the other remaining work
236.8 -> you need not to worry
238.116 -> so we will do the same in it also
239.695 -> What we will do
241.023 -> let us first try making
243.42 -> Okay
246.279 -> This is the matrix that we are given
248.21 -> in this we have to start rat from here
251.516 -> this is our visited
253.253 -> So initially all the visited will be 0
256.304 -> Because we haven't visited any place yet
258.385 -> Okay
260.594 -> Everything is 0 initially
263.466 -> now what we will do
264.775 -> we will come in starting
266.175 -> at this position. What we will do at this position
268.462 -> what we will do? we will follow lexographically
271.017 -> what is lexicographically
274.966 -> it means alphabetically
277.67 -> It will go like A, B,C ,D
278.85 -> either first D will come or l or R or U
282.122 -> Okay
282.817 -> So what we will do
283.655 -> first we will go down
284.867 -> then , when there will be no possibility of going down
287.537 -> We will try going left
288.648 -> when there will be no possibility of going left, then we will try going right
291.197 -> And if there will be no possibility of going right
293.262 -> so we will try going up
295.642 -> why are we doing it now
296.884 -> because the answer that we have to return
298.481 -> We have to return that lexicographically
300.339 -> So let us start from this position
302.494 -> we will start from 0,0
303.706 -> okay so let us explain one more thing
305.126 -> That what is the meaning of down
306.775 -> if you see, this is 0
308.799 -> this is 1, this is 2, this is 3
310.064 -> this is 0,1,2,3
312.275 -> Okay
312.951 -> this is your X co-ordinate
315.046 -> there is x this side
316.277 -> and this side y
317.014 -> right
317.575 -> Okay
318.223 -> So these are rows
320.278 -> And what are they? Column
323.09 -> these are columns
324.759 -> these all are columns
326.163 -> and these are rows
327.161 -> So when we have to go in next row
328.64 -> so what we will have to do to go to next row
330.106 -> we will have to do x+1
331.293 -> what we will have to do to come one row above
333.126 -> we will have to do x-1
334.329 -> this becomes down and this becomes up
336.344 -> similarly if we will have to go up
338.016 -> if we have to go left, that means we have to go behind
339.448 -> So what we will have to do
340.495 -> we will have to do minus 1 in y
342.641 -> and if we will have to go right , then we will have to do +1 in y
344.836 -> this becomes your left and this becomes your right
348.02 -> Okay
348.784 -> Now we will be requiring it again and again
350.8 -> Let just write it in advance
351.881 -> we will use directly from here
353.491 -> Now what we are doing
355.062 -> we are checking that if we go down
358.015 -> if going down is possible
359.231 -> Yes going down is possible
360.186 -> So what we do lets take a source x
363.173 -> and source y
364.18 -> Lets take source y
366.792 -> this is 0 and this is also 0
368.302 -> now what we will say we have to go down, if going down possible ?
370.368 -> is there 1 downside?
371.505 -> yes there is 1 downside
372.305 -> we will first mark this as visited 1
374.829 -> Okay we will mark this 1
377.549 -> and say you go down
379.075 -> this will go down
380.117 -> we will write down in path string
383.642 -> and do it +1
385.281 -> Okay
386.113 -> then we will check again
387.194 -> is it can go down again or not?
388.205 -> it can go down again
389.497 -> We will do visited the one that is before it
391.626 -> We will do it as 2
392.921 -> and do it down again
394.134 -> we will say it can again go down
396.463 -> Now it will say that it can go down again
398.149 -> this cannot go down again
399.362 -> because we have come here so we will ark this as visited
401.816 -> other than this we will say it cannot go down
404.171 -> lets try next thing
405.287 -> is it can go left?
406.359 -> it cannot left too because there is boundary there
408.695 -> then we will say that is it can go right?
409.909 -> yes it can go right
411.303 -> so go right
412.297 -> this will go write and we will do right here
413.919 -> what we will don it? we will do it as 1
415.502 -> So it can come on 2,1
416.961 -> After going on 2,1 , what it will say again
419.263 -> Now everything happened
420.74 -> now it will again start from 0
422.529 -> this will say can I again go down?
424.46 -> yes you can go down
426.117 -> lets go down then
427.495 -> if you can go down , then go down
429.161 -> who denied
430.074 -> so it will again go down
432.686 -> after going down , it will again say
434.475 -> that can I again go down
436.18 -> we did 3 for going down
438.544 -> it will say can I again go down?
439.716 -> you cannot go
440.56 -> because boundary arrived
441.523 -> if boundary arrived, then you cannot go down again
443.735 -> now it will say lets try next thing
445.124 -> can I go left?
446.258 -> there is 0 in left
447.7 -> so I cannot go left too
448.713 -> then it will say can I go right?
450.645 -> Yes you can go right
452.567 -> so go right again
453.898 -> this will go right
454.919 -> now we arrived at right
456.298 -> We will again start our call order
459.535 -> can I go down?
461.226 -> it will say you cannot go down
463.188 -> it is not possible because wall arrived
465.089 -> This will say can I go left?
466.648 -> It will say you cannot go left because we have come here form here
469.612 -> We came marking visited altogether
471.207 -> currently we are here
472.472 -> So it will say if my last one is visited?
474.407 -> we will say yes
475.652 -> because we had a condition here
477.085 -> that no cell can be visited more than one time
480.349 -> So we will check this
481.419 -> is 1 present at this visited position?
484.579 -> if not, then you cannot go back
486.207 -> absolutely not
487.149 -> so okay cannot go, you didn't leave a way
490.04 -> lets go on next
490.893 -> can I go right?
491.895 -> it will say lets see
493.863 -> our visited is at 0
495.401 -> is boundary crossing on right? no , it is not happening
497.306 -> So it will say that yes you can go right
500.358 -> so it will again go right
501.999 -> if it will go right
503.577 -> so it will check if have I come on 3,3
506.083 -> yes I have arrived on 3,3
508.585 -> so we got a path
510.502 -> Okay
512.275 -> now it will backtrack
513.293 -> it will backtrack, backtrack
514.748 -> okay
515.647 -> it will say I explored this path
518.54 -> I explored all of these paths
521.371 -> lets make it again
523.909 -> Okay
526.184 -> so we came from here
527.219 -> we came here
528.306 -> we went here form here
529.529 -> and then down
530.307 -> we went here from down
531.554 -> and from here to here
532.387 -> now it will say it will again go here
534.21 -> we had checked till right
535.655 -> it will say can I go up
537.009 -> it will say you cannot go up
538.828 -> there is 0 on up. okay no problem. If I cannot go up, then lets backtrack
542.343 -> then it will say again
544.066 -> can I go up?
545.132 -> it will say no you cannot go up
547.346 -> we have just come after visiting
548.671 -> okay so you cannot go up
550.237 -> it will again backtrack
552.463 -> It will come up
552.968 -> now it will say that can I go up now??
555.122 -> yes you can definitely go up
558.048 -> so it will say you go up
560.361 -> I went up
561.487 -> We unmarked all of these
564.114 -> we did them unvisited
565.247 -> and marked it as visited
566.335 -> it went up
567.998 -> it started again after going up
571.569 -> in order
572.195 -> it said can I go down?
574.8 -> it will say you have come from down
576.579 -> after visiting
577.357 -> you cannot go down. It will say can I go left?
578.868 -> there is visited in left too so you cannot go there as well
580.717 -> can I go right?
581.72 -> there is 0 on right so you cannot go
582.879 -> can I go up? there is 0 in up too so you cannot go there as well
584.715 -> it will say you didn't leave a way
586.976 -> lets backtrack again
588.766 -> cannot come here, we will come back
589.954 -> we will come here and say we explored all the paths
592.902 -> it will say go back
594.709 -> it will go down
596.085 -> it will say I also explored all the paths
597.905 -> I cannot go up and I have gone right already
600.077 -> it will say let me go back
601.299 -> Then we will come back to this position
603.352 -> what we did on this position
605.156 -> we just went down
606.087 -> we didn't explored left
607.693 -> so we will explore left
608.764 -> there is wall on left, so we cannot go
610.259 -> it will say try going right
611.626 -> so it will go right
613.247 -> Okay
613.986 -> this will say yes I can go right
615.766 -> and we unmarked all of them
618.906 -> Okay
619.763 -> so currently we are here
620.906 -> we have marked this
622.193 -> now it will say I can go right
623.559 -> lets go right
624.674 -> mark the right
625.62 -> and you go in right
626.574 -> now we will repeat the same cycle in right
629.115 -> we will say can I again go down
633.688 -> yes if you can go down, then go down
635.503 -> we will mark 1 the down one also
636.914 -> it will go down
637.736 -> We will keep writing altogether
638.876 -> where we were here
639.846 -> after down we went right
641.166 -> after that we gain went down
642.44 -> after that we will again follow the same path
644.575 -> down right, right
646.452 -> you can try doing by yourself
647.834 -> so what we did in it
648.961 -> we are moving in an order
650.282 -> what we are doing every time
651.584 -> we are applying 4 recursive calls
653.18 -> we are applying 4 recursive calls
656.067 -> down, then left, then right, then up
659.631 -> it goes again up from down
661.608 -> it keeps going down
663.743 -> we call it depth first search in one language
667.309 -> DFS
668.223 -> when we will study graphs and all, then we will understand it
670.22 -> what is its complete meaning
672.19 -> Okay
673.251 -> in this way we found all
674.963 -> other than this what we check
676.65 -> we check 4 conditions
678.121 -> if our index x is less than n
684.286 -> is it less than n
686.455 -> if it is not going down
688.284 -> we will say if we are not going, then it is good
689.935 -> if it is greater than 0
691.341 -> it should not go out in left too
693.988 -> right
694.691 -> yes right
695.755 -> then we do same thing for y
697.331 -> is it less than equal to n
698.979 -> we will say yes it is
700.549 -> if it is, then it is very good
701.652 -> if it is greater than 0
703.114 -> greater than equal to 0
704.537 -> if it is greater than equal to 0
706.137 -> yes it is
706.837 -> these 4 conditions plus
708.412 -> we check if visited of x,y is 0
714.217 -> if we haven't visited before
715.851 -> we will say yes we haven't done
717.163 -> plus we check
719.135 -> is there a wall here or not
720.482 -> so there is a matrix x,y
723.322 -> is there 1 or not
725.587 -> if there is 1
727.87 -> so we can go down
729.28 -> we check all these conditions
730.905 -> if all these conditions are correct
732.453 -> so we are safe
733.657 -> and if we are safe
734.679 -> so we will keep doing our work
736.36 -> thank you so much for watching this video
738.387 -> now we will write its code in the next video
740.727 -> and we will again dry run it and make you understand how things are working
743.364 -> thank you for watching
745.043 -> join the telegram channel if you haven't joined yet
746.787 -> let's meet in another video, till then bye
750.985 ->
Source: https://www.youtube.com/watch?v=CB25fIxE8P8