Simple BFS without extra memory


  • 0
    B
    class Solution {
    public:
        int POS[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<vector<int>> res(matrix.size(),vector<int>(matrix[0].size(),-1));
            queue<int> qu;
            for(int i=0;i<matrix.size();i++)
            {
                for(int j=0;j<matrix[0].size();j++)
                {
                    if(matrix[i][j] ==0)
                    {
                        res[i][j] = 0;
                        qu.push(i<<16|j);
                    }
                }
            }
            while(!qu.empty())
            {
                int temp = qu.front();
                qu.pop();
                int y = temp >>16;
                int x = temp & 0xFFFF;
                int dis = res[y][x];
                for(int n=0;n<4;n++)
                {
                    int y0 = y+POS[n][0];
                    int x0 = x+POS[n][1];
                    if(y0>=0 && y0<matrix.size() && x0>=0 && x0<matrix[0].size() && res[y0][x0]<0)
                    {
                        res[y0][x0] = dis+1;
                        qu.push(y0<<16|x0);
                    }
                }                            
            }
            return res;
        }
    };
    

Log in to reply
 

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