1from collections import deque
2class Solution:
3 def paintBooleanMatrix(self, x, y, image):
4 colour = image[x][y]
5 # return self.bfs(image, x, y, colour)
6 return self.dfs(image, x, y, colour)
7
8 def bfs(self, image, i, j, colour):
9 queue = deque([(i, j)])
10 image[i][j] = 0 if image[i][j] == 1 else 1
11 while queue:
12 i, j = queue.popleft()
13 for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
14 if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or image[x][y] != colour: continue
15 image[x][y] = 0 if image[i][j] == 1 else 1
16 queue.append((x, y))
17
18 def dfs(self, image, i, j, colour):
19 if i < 0 or i >= len(image) or j < 0 or j >= len(image[0]) or image[i][j] != colour: return
20 image[i][j] = 0 if image[i][j] == 1 else 1
21
22 for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: self.dfs(image, x, y, colour)