title: Find shortest path in maze with landmines and limited lives
body: <p>I've encountered a problem I'm having a bit of trouble solving. I am trying to write a program that solves an m by n grid maze that has landmines in it. The tricky part is that the player/maze runner has a L >= 1 number of lives, meaning they can step on a maximum of L - 1 landmines before they will die on the next landmine. </p>
  
  <p>Further details:</p>
  
  <p>-Each cell can be connected to any of the adjacent cells. All connections are two-way. </p>
  
  <p>-We can assume that the maze has a correct path from start to end given the number of lives.</p>
  
  <p>-The maze can contain loops or 'islands' where two paths from a given cell lead to the same cell.</p>
  
  <p>My current thoughts:</p>
  
  <p>I have tried a variety of approaches to this problem. There is the obvious brute force solution which involves traversing every possible path and taking the one with the lowest distance. But that is exponential time. I feel that there may be a Dijkstra-like or A*-like solution that leads to O(n + vlogv) time. Vanilla Dijkstra or A* do not lead to solutions for this problem since the state of the graph effectively changes depending on how it is traversed. I have also tried a variety of breadth first search + tracing back to start using priority queue. These schemes, after further investigation, can lead to exponential time.</p>
  
  <p>The most promising idea I've come up with so far involves parsing each maze into a graph and performing a modified Dijkstra. Each cell with three or more connections will be a node. Each cell with two connections is part of a path. Each cell with one connection can be discarded. The end result is a graph. You then perform something similar to Dijkstra, but I have not yet clarified a solution.</p>
  
  <p>I can only guess that this solution requires an algorithm that is efficient in the best case but can become exponential in the worst case.</p>