01 Matrix

Similar Problems:

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: 0 0 0 0 1 0 0 0 0 Output: 0 0 0 0 1 0 0 0 0

Example 2:

Input: 0 0 0 0 1 0 1 1 1 Output: 0 0 0 0 1 0 1 2 1

Note:

- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/01-matrix ## Basic Ideas: ## There are two types of 1: Adjacent nodes have 0; don't have ## ## BFS. ## Use type1 as layer 1. Mark it as -1. Then keep exploring the next level ## How to avoiding check one element twice? ## We have marked type1 as -1. So any processed positions will not be 1 any more. ## ## Complexity: Time O(m*n), Space O(1) import sys class Solution(object): def updateMatrix(self, matrix): """ :type matrix: List[List[int]] :rtype: List[List[int]] """ self.row_count = len(matrix) if self.row_count == 0: return matrix self.col_count = len(matrix[0]) queue = [] # mark elements which are 1 and also near 0 for i in xrange(self.row_count): for j in xrange(self.col_count): if matrix[i][j] == 1 and self.adjacentHasValue(matrix, i, j, 0): matrix[i][j] = -1 queue.append((i, j)) level = 2 while len(queue) != 0: for k in xrange(len(queue)): (i, j) = queue[0] del queue[0] # find neighbors for (offset_i, offset_j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]: next_i, next_j = i+offset_i, j+offset_j if next_i < 0 or next_i >= self.row_count or \ next_j <0 or next_j >= self.col_count: continue if matrix[next_i][next_j] == 1: matrix[next_i][next_j] = level queue.append((next_i, next_j)) level += 1 # change -1 back to 1 for i in xrange(self.row_count): for j in xrange(self.col_count): if matrix[i][j] == -1: matrix[i][j] = 1 return matrix def adjacentHasValue(self, matrix, i, j, value): if i!=0 and matrix[i-1][j] == value: return True if i!=self.row_count-1 and matrix[i+1][j] == value: return True if j!=0 and matrix[i][j-1] == value: return True if j!=self.col_count-1 and matrix[i][j+1] == value: return True return False # s = Solution() # matrix = [[1, 0, 0, 0], [1, 1, 1, 1], [1, 1, 1, 0]] # s.updateMatrix(matrix) # print matrix