Esiry.com
Focus on Machine Learning.

# LEETCODE 01 Matrix Problem

1 Description of the topic
Given a matrix whose element can only be 0 or 1, for each element in the matrix, calculate the distance of the element point from the nearest element 0 (the distance between two adjacent elements 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 a given matrix does not exceed 10,000;
The given matrix contains at least one zero;
Adjacent elements can only be connected up, down, left, or right.

Source of the topic:
https://leetcode.com/problems/01-matrix/

2 Solutions
In the pattern recognition for image recognition, when calculating the image fixed area feature, there is a concept of an integral map.
To solve this problem, borrow the concept and determine the distance between each element and the nearest element 0 as follows.

1) Scan the matrix once, calculate the sum of the values ​​of all the element points in the upper left corner of each element point, and the result is a sum value matrix called sumGraph;

2) For an element point of the original matrix, when calculating the distance from the nearest 0 element, first calculate whether the square area covered by the specified radius contains 0 according to sumGraph (calculate the sum of the element values ​​of the area according to sumGraph, if less than full 1 sum contains 0);

3) If the area contains 0, find a 0 in the area and calculate the nearest distance;

4) If the area does not contain 0, expand the search radius until you find a square area containing 0 and calculate the result as in step 3).

5) Scan the original matrix as in steps 2)-4) above and calculate the result until all element points are calculated and return to the result matrix.

Note:
In this paper, the initial search radius of the algorithm is 1. If the square area of ​​the radius up and down and left and right does not contain 0, the radius is doubled.
Gradually expand the radius and scan the full image as shown below.

3 Golang Implementation Code
https://github.com/olzhy/leetcode/blob/master/542_01_Matrix/test.go

```func updateMatrix(m [][]int) [][]int {
const MaxInt = 999999999

max := func(n1, n2 int) int {
if n1 >= n2 {
return n1
}
return n2
}

steps := func(x1, y1, x2, y2 int) int {
abs := func(a, b int) int {
c := a - b
if c < 0 { return -c } return c } return abs(x1, x2) + abs(y1, y2) } containsZero := func(sumGraph [][]int, x, y, radius int) bool { xMin, yMin, xMax, yMax := x-radius-1, y-radius-1, x+radius, y+radius if xMax > len(sumGraph)-1 {
xMax = len(sumGraph) - 1
}
if yMax > len(sumGraph[0])-1 {
yMax = len(sumGraph[0]) - 1
}

sumAllNotZeros := MaxInt
sum := sumAllNotZeros
if xMin < 0 && yMin < 0 {
sumAllNotZeros = (xMax + 1) * (yMax + 1)
sum = sumGraph[xMax][yMax]
} else if xMin < 0 && yMin >= 0 {
sumAllNotZeros = (xMax + 1) * (yMax - yMin)
sum = sumGraph[xMax][yMax] - sumGraph[xMax][yMin]
} else if xMin >= 0 && yMin < 0 {
sumAllNotZeros = (xMax - xMin) * (yMax + 1)
sum = sumGraph[xMax][yMax] - sumGraph[xMin][yMax]
} else {
sumAllNotZeros = (xMax - xMin) * (yMax - yMin)
sum = sumGraph[xMax][yMax] - sumGraph[xMin][yMax] - sumGraph[xMax][yMin] + sumGraph[xMin][yMin]
}
return sum < sumAllNotZeros
}

findMinStepsAround := func(m [][]int, x, y, radius int) int {
if xMin < 0 {
xMin = 0
}
if yMin < 0 { yMin = 0 } if xMax > len(m)-1 {
xMax = len(m) - 1
}
if yMax > len(m[0])-1 {
yMax = len(m[0]) - 1
}
minSteps := MaxInt
for i := xMin; i <= xMax; i++ {
for j := yMin; j <= yMax; j++ {
if 0 == m[i][j] {
steps := steps(x, y, i, j)
if steps < minSteps {
minSteps = steps
}
}
}
}
return minSteps
}

findMinStepsWithScalingRadius := func(m, sumGraph [][]int, x, y int) (int, int) {
minSteps := MaxInt
for r = minRadius; r <= maxRadius; r *= 2 { containsZero := containsZero(sumGraph, x, y, r) if containsZero { minSteps = findMinStepsAround(m, x, y, r) if minSteps > r {
continue
}
return minSteps, r
}
}
minSteps = findMinStepsAround(m, x, y, maxRadius)
}
return minSteps, r
}

sumGraph := func(m [][]int) [][]int {
sumGraph := make([][]int, len(m))
for i := range m {
sumGraph[i] = make([]int, len(m[i]))
for j := range m[i] {
sumGraph[i][j] = 0
if 0 == j && 0 == i {
sumGraph[i][j] = m[i][j]
} else if 0 == j && i > 0 {
sumGraph[i][j] = sumGraph[i-1][j] + m[i][j]
} else if j > 0 && 0 == i {
sumGraph[i][j] = sumGraph[i][j-1] + m[i][j]
} else {
sumGraph[i][j] = sumGraph[i][j-1] + sumGraph[i-1][j] - sumGraph[i-1][j-1] + m[i][j]
}
}
}
return sumGraph
}

sumG := sumGraph(m)
updated := make([][]int, len(m))
for i := range m {
updated[i] = make([]int, len(m[i]))
for j := range m[i] {
minSteps, _ := findMinStepsWithScalingRadius(m, sumG, i, j)
updated[i][j] = minSteps
}
}
return updated
}
```
Please indicate the source：Esiry » LEETCODE 01 Matrix Problem