/**
* @param {number[][]} grid
* @param {number} k
* @return {number}
*/
// O(mnk) time, O(mnk) space
var shortestPath = function(matrix, k) {
 const numRows = matrix.length;
 const numCols = matrix[0].length;

 // If there is only one empty cell in the matrix, we already reached the end
 if (numRows === 1 && numCols === 1) {
   return 0;
 }
 
 const queue = [];
 const visited = new Set();
 
 // Push the start cell to BFS from and mark it as visited
 
 // key = row-col-kRemaining
 visited.add(`0-0-${k}`);
 // [row, col, kRemaining, numSteps]
 queue.push([0,0,k,0]);	

 // BFS to see if we can make it to the end
 while (queue.length > 0) {
   const currentCell = queue.shift();
   const [currentRow, currentCol, kRemaining, numSteps] = currentCell;

   const directions = [[0,1],[1,0],[0,-1],[-1,0]];
   for (let direction of directions) {
     const [rowOffset, colOffset] = direction;
     const newRow = currentRow + rowOffset;
     const newCol = currentCol + colOffset;
     
     const isInBounds = newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols;
     if (!isInBounds) {
       continue;
     }
     
     // If we've encountered an obstacle and can eliminate it and we haven't visited it before
     if (matrix[newRow][newCol] === 1 && kRemaining > 0 && !visited.has(`${newRow}-${newCol}-${kRemaining-1}`)) {
       visited.add(`${newRow}-${newCol}-${kRemaining-1}`);
       queue.push([newRow, newCol, kRemaining - 1, numSteps + 1]);
     } else if (matrix[newRow][newCol] === 0 && !visited.has(`${newRow}-${newCol}-${kRemaining}`)) {
       // If we've reached the end, return the number of steps it took (should be the minimum for BFS)
       if (newRow === numRows - 1 && newCol === numCols - 1) {
         return numSteps + 1;
       }
       visited.add(`${newRow}-${newCol}-${kRemaining}`);
       queue.push([newRow, newCol, kRemaining, numSteps + 1]);
     }
   }
 }

 // Not possible to reach the end
 return -1;
};