concise c++ bfs solution that beats 90%


  • 0

    ···
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    //也可以正着来一遍,再反着来一遍
    int m = matrix.size(), n;
    if(m!=0)n = matrix[0].size();
    std::queue<pair<int,int>> q;
    for(int i=0;i<m;i++){
    for(int j=0; j<n;j++){
    if(matrix[i][j]==0)q.push({i,j});
    else matrix[i][j] = INT_MAX;
    }
    }
    while(!q.empty()){
    pair<int,int> cur = q.front();
    q.pop();
    int i = cur.first, j = cur.second, dis = matrix[i][j];
    if(i-1>=0 && matrix[i-1][j] > dis+1){matrix[i-1][j] = dis+1; q.push({i-1,j});}
    if(j-1>=0 && matrix[i][j-1] > dis+1){matrix[i][j-1] = dis+1; q.push({i,j-1});}
    if(i+1<m && matrix[i+1][j] > dis+1){matrix[i+1][j] = dis+1; q.push({i+1,j});}
    if(j+1<n && matrix[i][j+1] > dis+1){matrix[i][j+1] = dis+1; q.push({i,j+1});}
    }
    return matrix;
    }
    ···


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.