# Python BFS

• I was trying to use DFS to solve this problem during Contest, and got TLE. After reading https://discuss.leetcode.com/topic/83453/java-solution-bfs, I found how idiotic I am, why didn't I ever think about BFS?

Here is the solution using the same trick as https://discuss.leetcode.com/topic/29054/easiest-java-solution-with-explanation.

``````class Solution(object):
def helper(self, matrix, height, width, x, y):
dirs = ((0,1), (0,-1), (1,0), (-1,0))
queue = collections.deque([(x, y)])
step = 0
while queue:
for _ in xrange(len(queue)):
x, y = queue.popleft()
if x < 0 or x >= height or y < 0 or y >= width:
continue
if matrix[x][y] & 1 == 0:
return step
for d_x, d_y in dirs:
queue.append((x+d_x, y+d_y))
step += 1

def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
height = len(matrix)
width = len(matrix[0])
for i in xrange(height):
for j in xrange(width):
if matrix[i][j] != 0:
matrix[i][j] |= (self.helper(matrix, height, width, i, j) << 1)

for i in xrange(height):
for j in xrange(width):
if matrix[i][j] != 0:
matrix[i][j] >>= 1
return matrix
``````

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