[Java] Matrix path with at most K obstacle deletions

Given a MxN matrix of 0s and 1s where 1 is an obstacle, find the shortest path from 0,0 to M-1,N-1 (top left to bottom right) deleting at most K obstacles.

We for sure need a BFS, but need to tweak it a bit so we prefer fast paths that use as many deletions as other paths or fewer.

We therefore track for each cell the amount of deletions we have left when we reach it. If another path reached that cell before us AND had MORE deletions left, then the current path is not an optimal solution and we can discard it. This is because some faster (shorter) path exists that has higher chances of deleting obstacles down the road, so we should explore that path instead.

We use a queue of Integer[] to track the data we need: i, j, current path length, deletions left.

This gives us a O(MN) space and time solution.

You can check my implementation of shortestPathWithMaxKDeletions on my Gist, this time without tests because I am lazy so you can simply run leetcode instead.