# A/C Python solution, BFS, easy to understand, beat 21.16%

• class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
#print "matrix = ", matrix

``````    result = matrix
#print "result = ", result

numRows = len(matrix)
#print "numRows = ", numRows

if (numRows < 1):
return []
numCols = len(matrix[0])
if numCols < 1:
return []

#print "numCols = ", numCols

def verifyValidIndex(indexToValid):
rowIdx, colIdx = indexToValid

#print "in verifyValidIndex rowIdx = ", rowIdx, " colIdx = ", colIdx

if rowIdx < 0 or rowIdx >= numRows or colIdx < 0 or colIdx >= numCols:
#print "return False"
return False
else:
#print "return True"
return True

def bfs(curIdx, curDistance):
#print "bfs called, curIdx = ", curIdx, " curDistance = ", curDistance

curRowIdx, curColIdx = curIdx

dfsQueue = []
dfsQueue.append([curRowIdx, curColIdx, curDistance])

while (dfsQueue != []):
tmpNode = dfsQueue.pop(0)
tmpRowIdx, tmpColIdx, tmpDistance = tmpNode[0], tmpNode[1], tmpNode[2]
#print "tmpRowIdx = ", tmpRowIdx, " tmpColIdx = ", tmpColIdx, " tmpDistance = ", tmpDistance

if matrix[tmpRowIdx][tmpColIdx] == 0:
#print "found closest 0, tmpDistance = ", tmpDistance
dfsQueue = []
return tmpDistance
else:
#check up
newRowIdx, newColIdx = tmpRowIdx - 1, tmpColIdx
if verifyValidIndex([newRowIdx, newColIdx]) == True:
dfsQueue.append([newRowIdx, newColIdx, tmpDistance+1])
#check down
newRowIdx, newColIdx = tmpRowIdx + 1, tmpColIdx
if verifyValidIndex([newRowIdx, newColIdx]) == True:
dfsQueue.append([newRowIdx, newColIdx, tmpDistance+1])
#check left
newRowIdx, newColIdx = tmpRowIdx , tmpColIdx - 1
if verifyValidIndex([newRowIdx, newColIdx]) == True:
dfsQueue.append([newRowIdx, newColIdx, tmpDistance+1])
#check right
newRowIdx, newColIdx = tmpRowIdx , tmpColIdx + 1
if verifyValidIndex([newRowIdx, newColIdx]) == True:
dfsQueue.append([newRowIdx, newColIdx, tmpDistance+1])

# curDistance += 1
# print "1 curDistance = ", curDistance

for rowIdx in range(numRows):
for colIdx in range(numCols):
if (matrix[rowIdx][colIdx] == 1):
#print "rowIdx = ", rowIdx, " colIdx = ", colIdx
#print "this needs to do BFS"
distance = bfs([rowIdx, colIdx], 0)
#print "after bfs, distance = ", distance
result[rowIdx][colIdx] = distance

#print "after operation, result = ", result
return result``````

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