class Solution {
private:
    int n, m;
    int INF = INT_MAX;
    vector<vector<int>> ans;
    vector<pair<int, int>> dirs = { {-1,0}, {1,0}, {0,-1}, {0,1} };
    vector<bool> vis;
public:
    vector<vector<int>> updateMatrix(const vector<vector<int>>& matrix) {
        n = matrix.size();
        if(n != 0) m = matrix[0].size();

        ans.assign(n, vector<int>(m, INF));
        vis.assign(n*m, false);

        int i, j, i_, j_;
        queue<pair<int, int>> Q;
        for(i=0; i<n; ++i) for(j=0; j<m; ++j) {
            if(matrix[i][j] == 1) continue;

            ans[i][j] = 0;
            vis[i*m+j] = true;

            for(auto &d:dirs) {
                i_ = i + d.first;
                j_ = j + d.second;

                if(i_ < 0 || i_ >= n || j_ < 0 || j_ >= m || matrix[i_][j_] == 0 || vis[i_*m+j_]) continue;
                Q.push( {i_*m+j_, 1} );
                vis[i_*m+j_] = true;
                ans[i_][j_] = 1;
            }

        }


        while(!Q.empty()) {
            int x = Q.front().first;
            i = x/m;
            j = x%m;
            int dist = Q.front().second;
            Q.pop();

            for(auto &d:dirs) {
                i_ = i + d.first;
                j_ = j + d.second;
                if(i_ < 0 || i_ >= n || j_ < 0 || j_ >= m || vis[i_*m+j_]) continue;

                Q.push( {i_*m+j_, dist+1} );
                vis[i_*m+j_] = true;
                ans[i_][j_] = dist+1;
            }
        }

        return ans;
    }
};