# 1293. Shortest Path in a Grid with Obstacles Elimination
###### tags: `Leetcode` `Google` `Medium` `BFS`
Link: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
## 思路 $O(MNK)$ $O(MNK)$
正常bfs，queue里面除了要放位置，还要放当前的k
并且visited也要变成三维的，因为有可能多次访问一个位置，但是k不相同
## Code

class Solution {
    int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][][] visited = new boolean[m][n][k+1];
        q.add(new int[]{0,0,0});
        int depth = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                int[] curr = q.poll();
                if(curr[0]==m-1 && curr[1]==n-1) return depth;
                for(int j = 0;j < directions.length;j++){
                    int nextX = curr[0]+directions[j][0];
                    int nextY = curr[1]+directions[j][1];
                    int nextK = curr[2];
                    if(nextX>=0 && nextX<m && nextY>=0 && nextY<n){
                        if(grid[nextX][nextY]==1){
                            nextK++;
                        }
                        if(nextK<=k && !visited[nextX][nextY][nextK]){
                            visited[nextX][nextY][nextK] = true;
                            q.add(new int[]{nextX, nextY, nextK});
                        }
                    }
                }
            }
            depth++;
        }
        return -1;
    }
}