Backtracking | Rat in a maze (Easy)














































Backtracking | Rat in a maze (Easy)



BACKTRACKING-RAT IN A MAZE
PROBLEM STATEMENT

A rat is standing in the starting block mat[0][0] of a maze, a N*N matrix named as mat[N-1][N-1]. It has  to reach to the end of the matrix, mat[N-1][N-1]. In the maze matrix, 0 means the block is a dead end and 1 means the block can be used in the path from source to destination.  It can move in the following directions.

  • UP 
  • DOWN
  • LEFT
  • RIGHT

DIAGRAM

ALGORITHM

  1. Pass the matrix to shortestPath function, and create a visited matrix marking all the nodes as fase,i.e. unvisited
  2. Calling the backtrack matrix with all parameters
  3. Check if the node is valid, i.e. is not visited before and is satisfies the boundary conditions for the matrix
  4. If the position is reached return 0 
  5. marked the node as visited so that in the next step, if the node comes in path it will not create an infinite loop to the same node.
  6. Traverse to the left, right, up , and down cell of the matrix
  7. Mark the node as unvisited, in case the same node comes in the another path, it may not be declared as invalid.
  8. COMPLETED
 

CODE



OUTPUT:
The shortest path in the maze has: 8 nodes

More Articles of vinay chopra:

Name Views Likes
Project Ideas Advance Level-Web development 952 0
Subset of the Array | Backtracking 1139 0
C++ Difference between Vectors and Arrays 829 0
C++ Longest Common Subsequence | Dynamic Programming 2372 1
C++ String Compression | Google Interview 7715 0
C++ Climbing Stairs - LeetCode | dynamic programming 2769 0
BACKTRACKING | Introduction to backtracking 875 1
Project Ideas Intermediate Level-Web development 3192 1
C++ Right Side View of Binary Tree | BFS traversal 624 0
Reverse Integer | LeetCode 1371 1
C++ Two Sum LeetCode 21713 0
Sudoku solver | Backtracking 4278 1
Web development Project Ideas for beginners 834 0
Difference between dynamic programming and Backtracking 6967 1
Backtracking | Rat in a maze (Easy) 2224 1
C++ Minimum Number of Jumps to End | Dynamic Programming 666 1
DFS of Graph | PATH IN THE MAZE | Backtracking 2256 0
C++ Binary Tree Paths | Dfs | Backtracking 777 0
Partition Equal Subset Sum-LeetCode | BACKTRACKING 1628 0
C++ Maximum Size Subset with given Sum | Backtracking 1567 0
std::basic_file.is_open() 562 1
C++ Celebrity Problem | Backtracking 840 0
C++ std::basic_filebuf.close() 251 0
Coin Change Problem | Dynamic Programming 2264 0
Python To Compress an Image- Data Science 1146 1
C++ std::basic_file.open() 312 0
Must do Coding Questions for Tech Giants 1083 1

Comments