class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {

        int n = (int)grid.size();
        int m = (int)grid[0].size();

        queue<pair<int,int>>q;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == 2){
                    q.push({i, j});
                }
            }
        }

        int ans = 0;
        if(q.size()) ans--;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};

        while( !q.empty() ){

        queue<pair<int,int>>temp;
            int sz = q.size();
                ans++;

            for(int i=0;i<sz;i++){
                auto node = q.front();q.pop();
                int x = node.first;
                int y = node.second;

                for( int j=0;j<4;j++){
                    int nx = x+dx[j];
                    int ny = y+dy[j];

                    if(nx < 0 || ny < 0 || nx >=n || ny >=m )continue;
                    if(grid[nx][ny] == 0 || grid[nx][ny]==2)continue;
                    grid[nx][ny] = 2;

                    temp.push({nx, ny});
                }

            }

            q = temp;

        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j] == 1) return -1;
            }
        }

        return ans;

    }
};