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 {  
        xMin, yMin, xMax, yMax := x-radius, y-radius, x+radius, y+radius  
        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) {  
        minRadius, maxRadius := 1, max(max(x, y), max(len(m)-1-x, len(m)-1-y))  
        minSteps := MaxInt  
        r := minRadius  
        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  
            }  
        }  
        if maxRadius != 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  
}  

Your support will encourage us to be creative continuously!

Use [WeChat] Scan QR code for Appreciation

Use [Alipay] Scan QR code for Appreciation

Jumping to PayPal...
赞(0)
Please indicate the source:Esiry » LEETCODE 01 Matrix Problem

Comment 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址