12 FloodFill using DFS

[zwkcoding]

复习 DFS

class Solution {
public:
    int color = -1;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int new_color)  {
        if(color)== -1) color = image[sr][sc];
        if(image.empty() || sr == -1 || sr == image.size() || sc == -1 || sc == image[0].size() || image[sr][sc] != color || color == new_color) {
            return image;
        }
        image[sr][sc] = new_color;
        floodFill(image, sr - 1, sc, new_color);
        floodFill(image, sr + 1, sc, new_color);
        floodFill(image, sr, sc - 1, new_color);
        floodFill(image, sr, sc + 1, new_color);
        return image;
    }
};

[zwkcoding]

Distince Transform using BFS

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 x = xy.first, y = xy.second;
            for(auto d : dir)  {
                int xx = x + d.first, yy = y + d.second;
                if(xx < m && xx >= 0 && yy <  n && yy >= 0 )  {
                    // key idea
                    if(matrix[xx][yy] > matrix[x][y] + 1)  {
                        matrix[xx][yy] = matrix[x][y] + 1;
                        zeros.push({xx, yy});
                    }
                }
            } 
        }
        return matrix;
    }
};

you can try DFS!