542.01 矩阵

BFS

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int > > vc(rows, vector<int>(cols, 1000));
        queue<pair<int, int>> q;
        for(int i = 0; i < rows; ++i)
            for(int j = 0; j < cols; ++j)
            {
                if(!matrix[i][j]) {
                    q.push({i, j});
                    vc[i][j] = 0;
                }
            }
        int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(q.size()) {
            auto p = q.front();
            q.pop();
            int n = p.first;
            int m = p.second;
            int dist = vc[n][m];
            for(int i = 0; i < 4; ++i) {
                int nn = n + dir[i][0];
                int mm = m + dir[i][1];
                if(nn >=0 && mm >=0 && nn < rows && mm < cols) {
                    if(vc[nn][mm] > dist + 1) {
                        vc[nn][mm] = dist + 1;
                        q.push({nn, mm});
                    }
                }
            }
    
        }
        return vc;
    }
};

Accepted

48/48 cases passed (124 ms)

Your runtime beats 79.69 % of cpp submissions

Your memory usage beats 54.72 % of cpp submissions (23.4 MB)