Backtracking - Rat In A Maze Puzzle | Algorithms

Backtracking - Rat In A Maze Puzzle | Algorithms

by SJ · April 13, 2015 Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are blocked, means rat can­not enter into those cells. Rat can move in any direc­tion ( left, right, up and down). Input: A 2D-matrix with 0's and 1's fill in it. 0 means that cell is blocked and 1 means rat can move to that cell. Rat In A Maze Puzzle Approach: Cre­ate a solu­tion matrix of the same struc­ture as maze. When­ever rat moves to cell in a maze, mark that par­tic­u­lar cell in solu­tion matrix. At the end print the solu­tion matrix, fol­low that 1's from the top left cor­ner, it will be that path for the rat. Algo­rithm: print the solu­tion matrix.

Read full article from Backtracking - Rat In A Maze Puzzle | Algorithms