1730. Shortest Path to Get Food

T: O(mn)

S: O(mn)

class Solution {
    private static final int DIRS[][] = {{0,1}, {1, 0}, {0,-1}, {-1, 0}};
    public int getFood(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean hasFood = false;
        
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0 ; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '*') {
                    queue.offer(new int[]{i , j});    
                    visited[i][j] = true;
                } else if (grid[i][j] == 'X') {
                    visited[i][j] = true;
                } else if (grid[i][j] == '#') {
                    hasFood = true;
                }
            }
        }
        if (!hasFood) {
            return -1;
        }
        
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int[] cur = queue.poll();
                for (int[] dir : DIRS) {
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    if (!inArea(grid, x, y) || visited[x][y]) {
                        continue;
                    }
                    if (grid[x][y] == 'O') {
                        queue.offer(new int[]{x, y});
                        visited[x][y] = true;
                    } else if (grid[x][y] == '#') {
                        return step + 1;
                    }
                }
            }
            step++;
        }
        return -1;
    }
    private boolean inArea(char[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }
}