Rat in the maze

Given a NxN matrix with 0s and 1s. A block with value 0 is a dead end, we cannot use this block to move ahead. While a block with value 1 can be used to travel ahead in the matrix. Now, consider mat[0][0] as the starting point for the rat. We have to verify, if there exists a path in the matrix for the rat to reach the end.


Backtracking is a general algorithm for finding solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.