[C++] Clean Code - BFS queue


  • 0
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int m = matrix.size(), n = matrix[0].size(), maxdist = m + n;
            queue<pair<int, int>> q;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    matrix[i][j] == 0 ? q.push(make_pair(i, j)) : (void)(matrix[i][j] = maxdist);
    
            int delta[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1};
            while (!q.empty()) {
                pair<int, int> p = q.front();
                q.pop();
                int x = p.first, y = p.second;
                for (int d = 0; d < 4; d++) {
                    int x1 = x + delta[d][0], y1 = y + delta[d][1];
                    if (0 <= x1 && x1 < m && 0 <= y1 && y1 < n) {
                        if (matrix[x1][y1] == maxdist) q.push(make_pair(x1, y1));
                        matrix[x1][y1] = min(matrix[x1][y1], matrix[x][y] + 1);
                    }
                }
            }
            return matrix;
        }
    };
    

  • 0

    Here is my code, same idea.

    
    class Solution {
    private:
    	int M;
    	int N;
    	vector<pair<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    public:
    	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) 
    	{
    		M = matrix.size(), N = matrix[0].size();
    		vector<vector<bool>> visited(M, vector<bool>(N, false));
    		queue<pair<int, int>> q;
    		for (int x = 0; x < M; ++x)
    			for (int y = 0; y < N; ++y)
    				if (matrix[x][y] == 0)
    					q.push({ x, y });
    		while (!q.empty())
    		{
    			int size = q.size();
    			for (int i = 0; i < size; ++i)
    			{
    				int x = q.front().first;
    				int y = q.front().second;
    				q.pop();
    				for (auto &p : dirs)
    				{
    					int nx = x + p.first, ny = y + p.second;
    					if (nx >= 0 && nx < M && ny >= 0 && ny < N &&
    						matrix[nx][ny] == 1 && !visited[nx][ny])
    					{
    						q.push({ nx, ny });
    						matrix[nx][ny] = matrix[x][y] + 1;
    						visited[nx][ny] = true;
    					}
    				}
    			}
    		}
    		return matrix;
    	}
    };

Log in to reply
 

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