(01 BFS) 2290. Minimum Obstacle Removal to Reach Corner

class Solution {
    private static final int[][] DIRECTIONS = {{0,1}, {1, 0}, {0, -1}, {-1, 0}};
    private record Step(int x, int y, int cost){};

    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        Deque<Step> queue = new ArrayDeque<>();
        queue.offer(new Step(0, 0, 0));
        Set<String> visited = new HashSet<>();

        int[][] destCost = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(destCost[i], Integer.MAX_VALUE);
        }

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            String key = cur.x + "_" + cur.y;
            if (visited.contains(key)) {
                continue;
            }
            visited.add(key);
            // if (cur.x == m - 1 && cur.y == n - 1) {
            //     result = Math.min(result, cur.cost);
            // }

            for (int[] dir : DIRECTIONS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];

                if (x < 0 || x >= m || y < 0 || y >= n) {
                    continue;
                }

                int newCost = cur.cost + grid[x][y];
                if (destCost[x][y] > newCost) {
                    destCost[x][y] = newCost;
                    if (grid[x][y] == 1) {
                        queue.offerLast(new Step(x, y, newCost));
                    } else {
                        queue.offerFirst(new Step(x, y, newCost));
                    }
                }
            }
        }
        return destCost[m-1][n-1];
    }
}

/**
1. using Dihkstra
T: O(mnlogmn)
S: O(mn)

2. using 0-1 bfs, because there is only 0 and 1, so we can use a deque , if next is 0 put in deque head, 1 put in tail (maintain by yourself, not by pq)  
T: O(mn)
S: O(mn)

 */