[542. 01 Matrix] C++_BFS_queue


  • 2

    key: we should start from "0", and change "1" to INT_MAX in our original matrix.

    class Solution {
    public:
    vector<pair<int,int> > dir = {{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<int> > updateMatrix(vector<vector<int> >& matrix) {
        if(matrix.empty()) return matrix;
        int m = matrix.size();
        int n = matrix[0].size();
        queue<pair<int,int>> zeros;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == 0){
                    zeros.push({i,j});
                }else{
                    matrix[i][j] = INT_MAX;
                }
            }
        }
        while(!zeros.empty()){
            auto xy = zeros.front();
            zeros.pop();
            int i = xy.first, j = xy.second;
            for(auto d : dir){
                int ii = i + d.first, jj = j + d.second;
                if(ii < m && ii >= 0 && jj < n && jj >= 0){
                    if(matrix[ii][jj] >= matrix[i][j] + 1){
                        matrix[ii][jj] = matrix[i][j] + 1;
                        zeros.push({ii,jj});
                    }
                }
            }
        }
        return matrix;
    }
    };
    

    Of course here, we can use "vector" instead of "queue", but when the data is very large, the memory limit might be exceeded. So I recommend "queue".

    class Solution {
    public:
    vector<pair<int,int> > dir = {{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<int> > updateMatrix(vector<vector<int> >& matrix) {
        if(matrix.empty()) return matrix;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<pair<int,int>> zeros;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == 0){
                    zeros.push_back({i,j});
                }else{
                    matrix[i][j] = INT_MAX;
                }
            }
        }
        int pos = 0;
        while(pos < zeros.size()){
            auto xy = zeros[pos++];
            int i = xy.first, j = xy.second;
            for(auto d : dir){
                int ii = i + d.first, jj = j + d.second;
                if(ii < m && ii >= 0 && jj < n && jj >= 0){
                    if(matrix[ii][jj] >= matrix[i][j] + 1){
                        matrix[ii][jj] = matrix[i][j] + 1;
                        zeros.push_back({ii,jj});
                    }
                }
            }
        }
        return matrix;
    }
    

    };


  • 0
    S

    Do you know what the difference in complexity between your code and this is from? I get a time limit.

    int dx[] = {-1,1,0,0}; 
    int dy[] = {0,0,1,-1};
        
    class Solution {
    public:
        void dfs(vector<vector<int>>& ans, int i, int j, int value ){
            ans[i][j] = value;
            for(int k=0; k<4; k++){
                if(i + dx[k]>=0 && i +dx[k] < ans.size() && j + dy[k]>=0 && j + dy[k]< ans[0].size()){
                    if(ans[i + dx[k]][j + dy[k]]< value+1) continue;
                    dfs(ans, i + dx[k], j+dy[k], value+1);
                }
            }
            
        }
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<pair<int, int> > index;
            for(int i =0; i<matrix.size(); i++){
                for(int j =0; j<matrix[0].size();j++){
                    if(matrix[i][j] == 1){
                        matrix[i][j] = 10001;
                    }
                    else{
                        index.push_back(make_pair(i,j));
                    }
                }
            }
            
            for(int i =0; i<index.size(); i++){
              dfs(matrix,index[i].first, index[i].second, 0);
            }    
        
            return matrix; 
        }
        
    };
    
    
    
    

  • 1

    @sarakh
    Hi sara, the problem is that you use DFS rather than BFS.

    In your following code:

     if(i + dx[k]>=0 && i +dx[k] < ans.size() && j + dy[k]>=0 && j + dy[k]< ans[0].size()){
                if(ans[i + dx[k]][j + dy[k]]< value+1) continue;
                dfs(ans, i + dx[k], j+dy[k], value+1);
            }
    

    You will go into the DFS recursive function if there is any change in your matrix[i + dx[k]][j + dy[k]] (let's denote this cell as A), and you will change all of cells which are related with your A, and in the worst case, you will have to check all of the cells in your matrix and find out current minimized value for them.

    So each time you find a local minimized value for your current position, you might traverse all of the matrix, that's why you got TLE. Instead, if you use BFS, each time we store the cells which have the value change, we will never traverse every cells in our matrix, which saves lots of time.

    Is that clear for you?


  • 0
    S
    This post is deleted!

  • 0
    S

    @jasonshieh Oh yes I see! Thanks!


  • 0
    N

    Try to change

                    if(matrix[ii][jj] >= matrix[i][j] + 1){
                        matrix[ii][jj] = matrix[i][j] + 1;
                        zeros.push({ii,jj});
                    }
    

    into

                    if(matrix[ii][jj] > matrix[i][j] + 1){
                        matrix[ii][jj] = matrix[i][j] + 1;
                        zeros.push({ii,jj});
                    }
    

    this way, you will be faster and reduce some memery waste.


  • 0
    S
    This post is deleted!

Log in to reply
 

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