# Flood Fill

• 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;
}
``````

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

• 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``````

• This is textbook breadth-first search, not a depth-first.

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