Flood Fill


  • 0

    Click here to see the full article post


  • 0
    J

    c++, use a queue to loop through the possible connected pixels in the 4 directions. No helper function needed.

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    		int n = image.size(), m = image[0].size();
    		vector<pair<int, int>> dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, {0,1} };
    		queue<pair<int, int>> q;
    		pair<int, int> point(sr,sc);
    		q.push(point);
    		while (!q.empty()){
    			pair<int, int> t = q.front(); q.pop();
    			for (auto d : dirs){
    				int x = d.first + t.first, y = d.second + t.second;
    				if (x >= 0 && x < m && y >= 0 && y < m && image[x][y]==image[t.first][t.second]) {
    					q.push(pair<int,int> (x,y));
    				}
    			}
    			image[t.first][t.second] = newColor;
    		}
    		return image;
    	}
    

  • 0
    W

    The iterative solution should be optimal solution, as auxiliary queue memory is much smaller than the implicit call stack memory.


  • 0
    A

    iterative solution

    class Solution:

    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        if(image[sr][sc]==newColor):
            return image
        temp=image[sr][sc]
        stack=[(sr,sc)]
        while(stack):
            i,j=stack.pop()
            if(image[i][j]==temp):
                image[i][j]=newColor    
                if(i+1<len(image)):
                    stack.append((i+1,j))
                if(i-1>=0):
                    stack.append((i-1,j))
                if(j+1<len(image[0])):
                    stack.append((i,j+1))
                if(j-1>=0):
                    stack.append((i,j-1))
            else:
                pass
        return image

Log in to reply
 

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