class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

        if(matrix.empty()) return {{}};
        int n = (int)matrix.size();
        int m = (int)matrix[0].size();

        vector<vector<int>>ans(n, vector<int>(m, INT_MAX));
          queue<pair<int,int>>q;

        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};

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


        while( !q.empty() )
        {
            auto node = q.front();
            q.pop();

            int x = node.first;
            int y = node.second;

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

                if( nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

                if(ans[nx][ny]==INT_MAX)
                {
                    ans[nx][ny] = ans[x][y] + 1;
                    q.push({nx, ny});
                }

            }
        }

        return ans;

    }
};