shortest-path-to-get-food.cpp

// Time:  O(m * n)
// Space: O(m + n)

class Solution {
public:
    int getFood(vector<vector<char>>& grid) {
        static const vector<pair<int, int>> directions{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        vector<pair<int, int>> q;
        for (int r = 0; r < size(grid); ++r) {
            for (int c = 0; c < size(grid[0]); ++c) {
                if (grid[r][c] == '*') {
                    q.emplace_back(r, c);
                    break;
                }
            }
        }
        
        int result = 0;
        while (!empty(q)) {
            ++result;
            vector<pair<int, int>> new_q;
            for (const auto& [r, c] : q) {
                for (const auto& [dr, dc] : directions) {
                    int nr = r + dr, nc = c + dc;
                    if (!(0 <= nr && nr < size(grid) &&
                          0 <= nc && nc < size(grid[0]) &&
                          grid[nr][nc] != 'X')) {
                        continue;
                    }
                    if (grid[nr][nc] == '#') {
                        return result;
                    }
                    grid[nr][nc] = 'X';
                    new_q.emplace_back(nr, nc);
                }
            }
            q = move(new_q);
        }
        return -1;
    }
};