title: Backtracking - How do I solve this variant of "rat in a maze"?
body: <p>I recently appeared for a job interview where i was asked the popular RAT IN A MAZE PROBLEM where there is a maze represented by a 2 dimensional array which contains 0's and 1's for open paths and walls respectively and we have to print the shortest path.</p>
  
  <p>I solved the problem using backtracking and also printed all possible paths.</p>
  
  <p>But then the interviewer increased the toughness level and asked me to solve the same question with a new condition where the rat can trip "K" number of walls where K is input by the user.</p>
  
  <p>Now I tried a lot but couldn't figure out how to find the shortest path if tripping K walls was allowed.I thought whether it could be solved via DYNAMIC PROGRAMMING but couldn't implement it ultimately.</p>
  
  <p>The interviewer also didn't reveal the solution.
  Can anyone explain solution of this problem?</p>