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


  • 0
    W

    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

Log in to reply
 

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