Rat in Maze Puzzle : I was recently asked this question in an Interview.
http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/
I gave the interviewer the solution mentioned in the link which happens to be exponential.The interviewer was quite surprised by my response , and was apparently expecting a polynomial time solution.I looked for one but could not find any.Does there exist a polynomial time solution for this problem.