An image is represented by a 2-D array of integers, each integer representing the pixel value of the image.
Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.
To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.
Example 1:
Input: image = {{1,1,1},{1,1,0},{1,0,1}},
sr = 1, sc = 1, newColor = 2.
Output: {{2,2,2},{2,2,0},{2,0,1}}
Explanation: From the center of the image 
(with position (sr, sc) = (1, 1)), all 
pixels connected by a path of the same color
as the starting pixel are colored with the new 
color.Note the bottom corner is not colored 2, 
because it is not 4-directionally connected to 
the starting pixel.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function floodFill() which takes image, sr, sc and newColor as input paramater and returns the image after flood filling.
 
Expected Time Compelxity: O(n*m)
Expected Space Complexity: O(n*m)
 
Constraints:
1 <= n <= m <= 100
0 <= pixel values <= 10
0 <= sr <= (n-1)
0 <= sc <= (m-1)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Complete search

Matrices

Data structures

Starter code: class Solution:
	def floodFill(self, image, sr, sc, newColor):
		#Code here


Solutions:
from queue import Queue

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		q = Queue()
		q.put((sr, sc))
		visited = {}
		color = image[sr][sc]
		image[sr][sc] = newColor
		n = len(image)
		m = len(image[0])
		while not q.empty():
			(r, c) = q.get()
			visited[r, c] = True
			if visited.get((r - 1, c)) is None and r > 0 and (image[r - 1][c] == color):
				image[r - 1][c] = newColor
				visited[r - 1, c] = True
				q.put((r - 1, c))
			if visited.get((r + 1, c)) is None and r < n - 1 and (image[r + 1][c] == color):
				image[r + 1][c] = newColor
				visited[r + 1, c] = True
				q.put((r + 1, c))
			if visited.get((r, c - 1)) is None and c > 0 and (image[r][c - 1] == color):
				image[r][c - 1] = newColor
				visited[r, c - 1] = True
				q.put((r, c - 1))
			if visited.get((r, c + 1)) is None and c < m - 1 and (image[r][c + 1] == color):
				image[r][c + 1] = newColor
				visited[r, c + 1] = True
				q.put((r, c + 1))
		return image


class Solution:

	def floodFill(self, image, sr, sc, color):

		def dfs(sr, sc, image, color, row, cols, source):
			if sr >= row or sr < 0 or sc >= cols or (sc < 0):
				return
			if image[sr][sc] != source:
				return
			image[sr][sc] = color
			dfs(sr - 1, sc, image, color, row, cols, source)
			dfs(sr + 1, sc, image, color, row, cols, source)
			dfs(sr, sc - 1, image, color, row, cols, source)
			dfs(sr, sc + 1, image, color, row, cols, source)
		if image[sr][sc] == color:
			return image
		source = image[sr][sc]
		rows = len(image)
		cols = len(image[0])
		dfs(sr, sc, image, color, rows, cols, source)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		(m, n) = (len(image), len(image[0]))
		origColor = image[sr][sc]
		if origColor == newColor:
			return image

		def dfs(row, col):
			if row < 0 or row >= m or col < 0 or (col >= n):
				return
			if image[row][col] == origColor:
				image[row][col] = newColor
				dfs(row + 1, col)
				dfs(row, col + 1)
				dfs(row - 1, col)
				dfs(row, col - 1)
		dfs(sr, sc)
		return image


class Solution:

	def util(self, image, i, j, n, m, nc, c):
		if i < 0 or j < 0 or i >= n or (j >= m) or (image[i][j] == nc):
			return
		if image[i][j] == c:
			image[i][j] = nc
			self.util(image, i + 1, j, n, m, nc, c)
			self.util(image, i, j + 1, n, m, nc, c)
			self.util(image, i - 1, j, n, m, nc, c)
			self.util(image, i, j - 1, n, m, nc, c)

	def floodFill(self, image, sr, sc, newColor):
		color = image[sr][sc]
		n = len(image)
		m = len(image[0])
		self.util(image, sr, sc, n, m, newColor, color)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		seen = set()
		ROWS = len(image)
		COLS = len(image[0])
		oldColor = image[sr][sc]

		def recursive(r, c, seen):
			if image[r][c] != oldColor:
				return
			image[r][c] = newColor
			directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
			for (dr, dc) in directions:
				new_r = r + dr
				new_c = c + dc
				if new_r in range(ROWS) and new_c in range(COLS) and ((new_r, new_c) not in seen):
					seen.add((new_r, new_c))
					recursive(new_r, new_c, seen)
		recursive(sr, sc, seen)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):

		def dfs(ans, image, inicolor, newcolor, nrow, ncol, sr, sc):
			n = len(image)
			m = len(image[0])
			ans[sr][sc] = newcolor
			for i in range(4):
				nsr = sr + nrow[i]
				nsc = sc + ncol[i]
				if nsr >= 0 and nsr < n and (nsc >= 0) and (nsc < m) and (ans[nsr][nsc] != newColor) and (image[nsr][nsc] == inicolor):
					dfs(ans, image, inicolor, newcolor, nrow, ncol, nsr, nsc)
		ans = image
		nrow = [-1, 0, 1, 0]
		ncol = [0, 1, 0, -1]
		inicolor = image[sr][sc]
		dfs(ans, image, inicolor, newColor, nrow, ncol, sr, sc)
		return ans


from queue import Queue

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		m = len(image)
		n = len(image[0])
		isVisited = [[0 for j in range(n)] for i in range(m)]
		oldColor = image[sr][sc]
		q = Queue()
		q.put([sr, sc])
		isVisited[sr][sc] = 1
		image[sr][sc] = newColor
		while q.qsize() > 0:
			topNode = q.get()
			i = topNode[0]
			j = topNode[1]
			if i - 1 >= 0 and image[i - 1][j] == oldColor and (not isVisited[i - 1][j]):
				isVisited[i - 1][j] = 1
				image[i - 1][j] = newColor
				q.put([i - 1, j])
			if i + 1 < m and image[i + 1][j] == oldColor and (not isVisited[i + 1][j]):
				isVisited[i + 1][j] = 1
				image[i + 1][j] = newColor
				q.put([i + 1, j])
			if j - 1 >= 0 and image[i][j - 1] == oldColor and (not isVisited[i][j - 1]):
				isVisited[i][j - 1] = 1
				image[i][j - 1] = newColor
				q.put([i, j - 1])
			if j + 1 < n and image[i][j + 1] == oldColor and (not isVisited[i][j + 1]):
				isVisited[i][j + 1] = 1
				image[i][j + 1] = newColor
				q.put([i, j + 1])
		return image


import itertools
from collections import deque

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		ans = image
		iniColor = image[sr][sc]
		n = len(image)
		m = len(image[0])
		delRow = [-1, 0, +1, 0]
		delCol = [0, +1, 0, -1]
		visited = [[None for _ in range(m)] for _ in range(n)]

		def bfs(row, col):
			q = deque()
			ans[row][col] = newColor
			visited[row][col] = 1
			q.append((row, col))
			while q:
				(newRow, newCol) = q.popleft()
				for i in range(4):
					nRow = newRow + delRow[i]
					nCol = newCol + delCol[i]
					if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (image[nRow][nCol] == iniColor) and (visited[nRow][nCol] is None):
						visited[nRow][nCol] = 1
						ans[nRow][nCol] = newColor
						q.append((nRow, nCol))
		bfs(sr, sc)
		return ans


import itertools

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		ans = image
		iniColor = image[sr][sc]
		n = len(image)
		m = len(image[0])
		delRow = [-1, 0, +1, 0]
		delCol = [0, +1, 0, -1]
		visited = [[None for _ in range(m)] for _ in range(n)]

		def dfs(row, col):
			ans[row][col] = newColor
			visited[row][col] = 1
			for i in range(4):
				nRow = row + delRow[i]
				nCol = col + delCol[i]
				if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (image[nRow][nCol] == iniColor) and (visited[nRow][nCol] is None):
					dfs(nRow, nCol)
		dfs(sr, sc)
		return ans


from collections import deque

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		dirx = [[-1, 0], [0, 1], [0, -1], [1, 0]]
		n = len(image)
		m = len(image[0])

		def isvalid(i, j):
			if i >= 0 and i < n and (j >= 0) and (j < m):
				return 1
			return 0
		dq = deque([])
		dq.append((sr, sc))
		prevcolr = image[sr][sc]
		visited = [[0] * m for _ in range(n)]
		visited[sr][sc] = 1
		while dq:
			(i, j) = dq.pop()
			image[i][j] = newColor
			for (x, y) in dirx:
				if isvalid(i + x, j + y) and (not visited[i + x][j + y]) and (image[i + x][j + y] == prevcolr):
					visited[i + x][j + y] = 1
					dq.append((i + x, j + y))
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		row = len(image)
		col = len(image[0])
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		visited = [[-1 for _ in range(col)] for _ in range(row)]
		queue = [(sr, sc, image[sr][sc])]
		visited[sr][sc] = 1
		while queue:
			(x, y, color) = queue.pop(0)
			for (i, j) in directions:
				new_x = x + i
				new_y = y + j
				if new_x >= 0 and new_y >= 0 and (new_x < row) and (new_y < col) and (visited[new_x][new_y] == -1) and (image[new_x][new_y] == color):
					visited[new_x][new_y] = 1
					queue.append((new_x, new_y, image[new_x][new_y]))
		for i in range(row):
			for j in range(col):
				if visited[i][j] == 1:
					image[i][j] = newColor
		return image


from collections import deque

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		queue = deque()
		queue.append([sr, sc])
		color = image[sr][sc]
		m = len(image)
		n = len(image[0])
		while queue:
			(x, y) = queue.popleft()
			if image[x][y] == newColor:
				continue
			image[x][y] = newColor
			for (i, j) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
				if 0 <= x + i < m and 0 <= y + j < n and (image[x + i][y + j] == color):
					queue.append([x + i, y + j])
		return image


class Solution:

	def dfs(self, row, col, ans, image, newColor, delRow, delCol, iniColor):
		ans[row][col] = newColor
		(n, m) = (len(image), len(image[0]))
		for i in range(4):
			(nrow, ncol) = (row + delRow[i], col + delCol[i])
			if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (image[nrow][ncol] == iniColor) and (ans[nrow][ncol] != newColor):
				self.dfs(nrow, ncol, ans, image, newColor, delRow, delCol, iniColor)

	def floodFill(self, image, sr, sc, newColor):
		iniColor = image[sr][sc]
		ans = image
		delRow = [-1, 0, 1, 0]
		delCol = [0, 1, 0, -1]
		self.dfs(sr, sc, ans, image, newColor, delRow, delCol, iniColor)
		return ans


class Solution:

	def floodFill(self, image, sr, sc, new):
		color = image[sr][sc]
		if color == new:
			return image

		def dfs(i, j):
			queue = [(i, j)]
			while len(queue):
				(i, j) = queue.pop()
				image[i][j] = new
				dirx = [-1, 1, 0, 0]
				diry = [0, 0, -1, 1]
				for ele in range(4):
					newx = i + dirx[ele]
					newy = j + diry[ele]
					if newx in range(len(image)) and newy in range(len(image[0])) and (image[newx][newy] == color):
						queue.append((newx, newy))
		dfs(sr, sc)
		return image


class Solution:

	def floodFill(self, image, sr, sc, new):
		color = image[sr][sc]

		def dfs(i, j):
			if i not in range(0, len(image)) or j not in range(0, len(image[0])) or image[i][j] != color or (image[i][j] == new):
				return
			image[i][j] = new
			dfs(i - 1, j)
			dfs(i, j - 1)
			dfs(i, j + 1)
			dfs(i + 1, j)
		dfs(sr, sc)
		return image


class Solution:

	def dfs(self, image, i, j, m, n, oldColor, newColor, visited):
		if i < 0 or j < 0 or i >= m or (j >= n):
			return
		if visited[i][j] == True:
			return
		visited[i][j] = True
		if image[i][j] != oldColor:
			return
		image[i][j] = newColor
		self.dfs(image, i - 1, j, m, n, oldColor, newColor, visited)
		self.dfs(image, i, j - 1, m, n, oldColor, newColor, visited)
		self.dfs(image, i + 1, j, m, n, oldColor, newColor, visited)
		self.dfs(image, i, j + 1, m, n, oldColor, newColor, visited)

	def floodFill(self, image, sr, sc, newColor):
		visited = []
		(m, n) = (len(image), len(image[0]))
		for i in range(m):
			temp = []
			for j in range(n):
				temp.append(False)
			visited.append(temp)
		oldColor = image[sr][sc]
		self.dfs(image, sr, sc, m, n, oldColor, newColor, visited)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		mycolor = image[sr][sc]

		def helper(sr, sc):
			if sr < 0 or sr >= len(image) or sc < 0 or (sc >= len(image[0])):
				return
			if image[sr][sc] != mycolor:
				return
			if image[sr][sc] == newColor:
				return
			image[sr][sc] = newColor
			helper(sr - 1, sc)
			helper(sr + 1, sc)
			helper(sr, sc - 1)
			helper(sr, sc + 1)
		helper(sr, sc)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		vis = [[0 for i in range(len(image[0]))] for j in range(len(image))]
		(m, n) = (len(image), len(image[0]))

		def bfs(vis, image, sr, sc, newColor, help):
			image[sr][sc] = newColor
			vis[sr][sc] = 1
			queue = []
			queue.append([sr, sc])
			while queue:
				curr = queue.pop(0)
				(row, col) = (curr[0], curr[1])
				for i in range(4):
					(nrow, ncol) = (row + drow[i], col + dcol[i])
					if nrow >= 0 and ncol >= 0 and (nrow < m) and (ncol < n) and (vis[nrow][ncol] == 0) and (image[nrow][ncol] == help):
						vis[nrow][ncol] = 1
						image[nrow][ncol] = newColor
						queue.append([nrow, ncol])
		bfs(vis, image, sr, sc, newColor, image[sr][sc])
		return image


class Solution:

	def floodFill(self, image, sr, sc, color):
		r = len(image)
		c = len(image[0])

		def dfs(i, j):
			if i < 0 or j < 0 or i >= r or (j >= c) or (image[i][j] == color) or (image[i][j] != pre):
				return
			image[i][j] = color
			dfs(i + 1, j)
			dfs(i - 1, j)
			dfs(i, j + 1)
			dfs(i, j - 1)
		pre = image[sr][sc]
		dfs(sr, sc)
		return image


class Solution:

	def floodFill(self, a, sr, sc, newColor):
		color = a[sr][sc]
		q = [(sr, sc)]
		a[sr][sc] = newColor
		vis = [[0 for i in range(len(a[0]))] for i in range(len(a))]
		vis[sr][sc] = 1
		while len(q) != 0:
			(row, col) = q.pop(0)
			for i in [-1, 1]:
				if row + i >= 0 and row + i < len(a):
					if a[row + i][col] == color and vis[row + i][col] == 0:
						vis[row + i][col] = 1
						a[row + i][col] = newColor
						q.append((row + i, col))
				if col + i >= 0 and col + i < len(a[0]):
					if a[row][col + i] == color and vis[row][col + i] == 0:
						vis[row][col + i] = 1
						a[row][col + i] = newColor
						q.append((row, col + i))
		return a


class Solution:

	def dfs(self, grid, i, j, newColor, val):
		if i >= 0 and i < len(grid) and (j >= 0) and (j < len(grid[i])) and (grid[i][j] == val):
			grid[i][j] = newColor
			self.dfs(grid, i - 1, j, newColor, val)
			self.dfs(grid, i + 1, j, newColor, val)
			self.dfs(grid, i, j + 1, newColor, val)
			self.dfs(grid, i, j - 1, newColor, val)

	def floodFill(self, image, sr, sc, newColor):
		if image[sr][sc] != newColor:
			self.dfs(image, sr, sc, newColor, image[sr][sc])
		return image


class Solution:

	def isValid(self, i, j, image, mapp, old, new):
		if i < 0 or j < 0 or i == len(image) or (j == len(image[0])) or (image[i][j] == new) or ((i, j) in mapp) or (image[i][j] not in [old, new]):
			return False
		return True

	def floodFill(self, image, sr, sc, new):
		old = image[sr][sc]
		mapp = {}
		mapp[sr, sc] = True
		image[sr][sc] = new
		queue = [[sr, sc]]
		while queue:
			x = queue.pop(0)
			(i, j) = (x[0], x[1])
			if self.isValid(i + 1, j, image, mapp, old, new):
				queue.append([i + 1, j])
				mapp[i + 1, j] = True
				image[i + 1][j] = new
			if self.isValid(i, j - 1, image, mapp, old, new):
				queue.append([i, j - 1])
				mapp[i, j - 1] = True
				image[i][j - 1] = new
			if self.isValid(i, j + 1, image, mapp, old, new):
				queue.append([i, j + 1])
				mapp[i, j + 1] = True
				image[i][j + 1] = new
			if self.isValid(i - 1, j, image, mapp, old, new):
				queue.append([i - 1, j])
				mapp[i - 1, j] = True
				image[i - 1][j] = new
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):

		def dfs(i, j, val, newColor):
			if i < 0 or i >= rows or j < 0 or (j >= cols) or (image[i][j] != val):
				return
			image[i][j] = newColor
			dfs(i - 1, j, val, newColor)
			dfs(i + 1, j, val, newColor)
			dfs(i, j - 1, val, newColor)
			dfs(i, j + 1, val, newColor)
		(rows, cols) = (len(image), len(image[0]))
		val = image[sr][sc]
		if val != newColor:
			dfs(sr, sc, val, newColor)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):

		def dfs(row, col, newColor, sr, sc, sourse, image):
			if sr < 0 or sr >= row or sc < 0 or (sc >= col):
				return
			if sourse != image[sr][sc]:
				return
			else:
				image[sr][sc] = newColor
				dfs(row, col, newColor, sr - 1, sc, sourse, image)
				dfs(row, col, newColor, sr + 1, sc, sourse, image)
				dfs(row, col, newColor, sr, sc - 1, sourse, image)
				dfs(row, col, newColor, sr, sc + 1, sourse, image)
		if image[sr][sc] == newColor:
			return image
		else:
			dfs(len(image), len(image[0]), newColor, sr, sc, image[sr][sc], image)
			return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):

		def dfs(image, sr, sc, newColor, srl, scl, source):
			if sr < 0 or sr >= srl or sc < 0 or (sc >= scl):
				return
			if image[sr][sc] != source:
				return
			image[sr][sc] = newColor
			dfs(image, sr - 1, sc, newColor, srl, scl, source)
			dfs(image, sr + 1, sc, newColor, srl, scl, source)
			dfs(image, sr, sc - 1, newColor, srl, scl, source)
			dfs(image, sr, sc + 1, newColor, srl, scl, source)
		srl = len(image)
		scl = len(image[0])
		source = image[sr][sc]
		if image[sr][sc] == newColor:
			return image
		else:
			dfs(image, sr, sc, newColor, srl, scl, source)
			return image


from collections import deque

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		initial = image[sr][sc]
		n = len(image)
		m = len(image[0])
		vis = [[0 for j in range(m)] for i in range(n)]

		def dfs(r, c, vis, image):
			vis[r][c] = 1
			image[r][c] = newColor
			dr = [-1, 1, 0, 0]
			dc = [0, 0, -1, 1]
			for k in range(len(dr)):
				nr = r + dr[k]
				nc = c + dc[k]
				if 0 <= nr < n and 0 <= nc < m and (vis[nr][nc] == 0) and (image[nr][nc] == initial):
					dfs(nr, nc, vis, image)
			return
		for i in range(n):
			for j in range(m):
				if i == sr and j == sc:
					dfs(i, j, vis, image)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		inicol = image[sr][sc]
		ans = [row[:] for row in image]
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		self.dfs(image, sr, sc, newColor, delrow, delcol, inicol, ans)
		return ans

	def dfs(self, image, row, col, newColor, delrow, delcol, inicol, ans):
		ans[row][col] = newColor
		r = len(image)
		c = len(image[0])
		for i in range(4):
			nrow = row + delrow[i]
			ncol = col + delcol[i]
			if nrow >= 0 and nrow < r and (ncol >= 0) and (ncol < c) and (ans[nrow][ncol] == inicol) and (ans[nrow][ncol] != newColor):
				self.dfs(image, nrow, ncol, newColor, delrow, delcol, inicol, ans)


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		sourceColor = image[sr][sc]
		if newColor == sourceColor:
			return image
		self.dfs(image, sr, sc, sourceColor, newColor)
		return image

	def dfs(self, image, sr, sc, sourceColor, newColor):
		if 0 <= sr < len(image) and 0 <= sc < len(image[0]) and (image[sr][sc] != newColor) and (image[sr][sc] == sourceColor):
			image[sr][sc] = newColor
			self.dfs(image, sr + 1, sc, sourceColor, newColor)
			self.dfs(image, sr - 1, sc, sourceColor, newColor)
			self.dfs(image, sr, sc + 1, sourceColor, newColor)
			self.dfs(image, sr, sc - 1, sourceColor, newColor)


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		m = len(image)
		n = len(image[0])
		startcolor = image[sr][sc]
		visited = []
		for i in range(m):
			visited.append([0] * n)
		self.dfs(sr, sc, visited, image, newColor, startcolor)
		return image

	def dfs(self, i, j, visited, image, color, startcol):
		m = len(image)
		n = len(image[0])
		if i < 0 or i > m - 1 or j < 0 or (j > n - 1) or (image[i][j] != startcol):
			return
		if visited[i][j]:
			return
		visited[i][j] = 1
		image[i][j] = color
		return self.dfs(i - 1, j, visited, image, color, startcol) or self.dfs(i, j + 1, visited, image, color, startcol) or self.dfs(i + 1, j, visited, image, color, startcol) or self.dfs(i, j - 1, visited, image, color, startcol)


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		n = len(image)
		m = len(image[0])
		ini = image[sr][sc]
		vis = [[0 for j in range(m)] for i in range(n)]
		queue = []
		queue.append((sr, sc))
		vis[sr][sc] = 1
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		while len(queue) > 0:
			e = queue.pop(0)
			r = e[0]
			c = e[1]
			image[r][c] = newColor
			for i in range(4):
				nrow = r + delrow[i]
				ncol = c + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (image[nrow][ncol] == ini) and (vis[nrow][ncol] == 0):
					queue.append((nrow, ncol))
					vis[nrow][ncol] = 1
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		src_pixel = image[sr][sc]
		self.helper(image, sr, sc, newColor, len(image), len(image[0]), src_pixel)
		return image

	def helper(self, image, cur_i, cur_j, newColor, rows, cols, src_pixel):
		if cur_i < 0 or cur_i >= rows:
			return
		if cur_j < 0 or cur_j >= cols:
			return
		if image[cur_i][cur_j] != src_pixel:
			return
		if image[cur_i][cur_j] == newColor:
			return
		image[cur_i][cur_j] = newColor
		self.helper(image, cur_i + 1, cur_j, newColor, rows, cols, src_pixel)
		self.helper(image, cur_i - 1, cur_j, newColor, rows, cols, src_pixel)
		self.helper(image, cur_i, cur_j + 1, newColor, rows, cols, src_pixel)
		self.helper(image, cur_i, cur_j - 1, newColor, rows, cols, src_pixel)


from collections import deque

class Solution:

	def floodFill(self, image, sr, sc, newColor):
		grid = image[:]
		q = deque()
		q.append([sr, sc])
		ini_colr = image[sr][sc]
		while len(q):
			p = q.popleft()
			grid[p[0]][p[1]] = newColor
			k = p[0]
			l = p[1]
			for a in range(-1, 2):
				for b in range(-1, 2):
					if a != b and a + b != 0:
						row = k + a
						col = l + b
						if row >= 0 and col >= 0 and (row < len(grid)) and (col < len(grid[0])) and (image[row][col] == ini_colr) and (grid[row][col] != newColor):
							q.append([row, col])
							grid[row][col] = newColor
		return grid


class Solution:

	def floodFill(self, image, sr, sc, newColor):

		def perform(a, b, visited=set()):
			if (a, b) in visited:
				return
			if a < 0 or b < 0:
				return
			if a >= len(image) or b >= len(image[0]):
				return
			if image[a][b] == color:
				visited.add((a, b))
				image[a][b] = newColor
				perform(a, b + 1, visited)
				perform(a, b - 1, visited)
				perform(a + 1, b, visited)
				perform(a - 1, b, visited)
		color = image[sr][sc]
		perform(sr, sc)
		return image


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		initclr = image[sr][sc]
		new_image = image
		srn = len(image)
		scn = len(image[0])
		delsr = [-1, +1, 0, 0]
		delsc = [0, 0, +1, -1]

		def dfs(image, sr, sc, new_image, newcolor, initclr):
			new_image[sr][sc] = newcolor
			for i in range(4):
				nsr = sr + delsr[i]
				nsc = sc + delsc[i]
				if nsr < srn and nsc < scn and (nsr > -1) and (nsc > -1) and (image[nsr][nsc] == initclr) and (new_image[nsr][nsc] != newColor):
					new_image[nsr][nsc] = newcolor
					dfs(image, nsr, nsc, new_image, newColor, initclr)
		dfs(image, sr, sc, new_image, newColor, initclr)
		return new_image


class Solution:

	def floodFill(self, adj, sr, sc, newColor):
		x = len(adj[0])
		y = len(adj)
		visited = [[0] * x for i in range(y)]
		q = [[sr, sc]]
		ptr = 0
		curr = adj[sr][sc]
		adj[sr][sc] = newColor
		visited[sr][sc] = 1
		while ptr < len(q):
			node = q[ptr]
			for a in range(-1, 2):
				for b in range(-1, 2):
					try:
						if abs(a) != abs(b) and (not (a == b and a != 0)) and (node[0] - a >= 0) and (node[1] - b >= 0) and (adj[node[0] - a][node[1] - b] == curr) and (visited[node[0] - a][node[1] - b] == 0):
							visited[node[0] - a][node[1] - b] = 1
							adj[node[0] - a][node[1] - b] = newColor
							q.append([node[0] - a, node[1] - b])
					except:
						pass
			ptr += 1
		return adj


from collections import deque

def dfs(r, c, grid, old, new, visit):
	visit[r][c] = 1
	(n, m) = (len(grid), len(grid[0]))
	grid[r][c] = new
	l = [[-1, 0], [1, 0], [0, 1], [0, -1]]
	for (i, j) in l:
		(nr, nc) = (r + i, c + j)
		if nr < n and nr >= 0 and (nc < m) and (nc >= 0) and (grid[nr][nc] == old) and (not visit[nr][nc]):
			dfs(nr, nc, grid, old, new, visit)

class Solution:

	def floodFill(self, grid, sr, sc, new):
		old = grid[sr][sc]
		(n, m) = (len(grid), len(grid[0]))
		visit = [[0] * m for _ in range(n)]
		dfs(sr, sc, grid, old, new, visit)
		return grid


class Solution:

	def floodFill(self, image, sr, sc, newColor):
		original_color = image[sr][sc]
		if original_color == newColor:
			return image

		def fill(image, row, col):
			if row < 0 or row >= len(image) or col < 0 or (col >= len(image[0])) or (image[row][col] != original_color):
				return
			image[row][col] = newColor
			fill(image, row + 1, col)
			fill(image, row, col + 1)
			fill(image, row - 1, col)
			fill(image, row, col - 1)
		fill(image, sr, sc)
		return image