13. Range of Motion of robot (DFS and optimization, Diagram BFS)

The title

There is a square on the ground with m rows and n columns, from the coordinates [0,0] to the coordinates [m-1,n-1].

A robot starting from a cell with the coordinates [0, 0] can move one cell to the left, right, up, or down at a time (not to the square), and cannot enter a cell where the sum of the rows and columns is greater than k.

For example, when K is 18, the robot can enter the grid [35, 37] because 3+5+3+7=18. But it cannot enter the grid [35, 38] because 3+5+3+8=19. How many cells can the robot reach?

Example 1:

Enter: m =2, n = 3, k = 1Output:3
Copy the code

Example 2:

Enter: m =3, n = 1, k = 0Output:1
Copy the code

Tip:

1 <= n,m <= 100
0 <= k <= 20
Copy the code

Source: LeetCode

Link: leetcode-cn.com/problems/ji…

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

A, analysis,

There are generally two ways of thinking about matrix search problems:

It’s done recursivelyDepth-first DFS
- To the end in one direction, then back
With the queue implementationBreadth-first BFS
- Search forward by “flat push”

Solution 1: DFS depth first and optimization

func movingCount(_ m: Int._ n: Int._ k: Int) -> Int {
    if m < = 0 || n < = 0 || k < 0 {
        return 0
    }
    var flags: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: m)
    return moveTo(0.0, k, flags: &flags)
}
Copy the code

2.1 Core recursive logic

func moveTo(_ x: Int._ y: Int._ k: Int.flags: inout [[Bool]]) -> Int {
    if (x < 0 || x > = flags.first?.count ?? 0) ||
        (y < 0 || y > = flags.count) ||
        (flags[y][x] = = true) ||
        (digitSum(x) + digitSum(y) > k)
    {
        return 0
    }
    
    flags[y][x] = true
    
    let count = 1
        + moveTo(x + 1, y, k, flags: &flags)
        + moveTo(x - 1, y, k, flags: &flags)
        + moveTo(x, y + 1, k, flags: &flags)
        + moveTo(x, y - 1, k, flags: &flags)
    
    return count
}
Copy the code

2.2 Digits and functions

func digitSum(_ num: Int) -> Int {
    var temp = num
    var result = 0
    while temp > 0 {
        result + = temp % 10
        temp = Int(floor(Double(temp) / 10.0))}return result
}
Copy the code

2.3 summarize

Time complexity
- The worst O (m * n)
Spatial complexity
- The worst O (m * n)

3. DFS optimization

In the depth-first solution, we split it into four subproblems: up, down, left and right.

But in fact you only need to go in the lower right direction, because you must have gone up and left.

Optimized core moveTo code:

func moveTo(_ x: Int._ y: Int._ k: Int.flags: inout [[Bool]]) -> Int {
    if (x < 0 || x > = flags.first?.count ?? 0) ||
        (y < 0 || y > = flags.count) ||
        (flags[y][x] = = true) ||
        (digitSum(x) + digitSum(y) > k)
    {
        return 0
    }
    
    flags[y][x] = true
    
    let count = 1
        + moveTo(x + 1, y, k, flags: &flags)
        + moveTo(x, y + 1, k, flags: &flags)
    
    return count
}
Copy the code

You can see that the reduction of redundant computing efficiency increases a lot, which is a good plus if you notice it during the interview

Four, solution two: breadth first

Breadth – first solution is less intuitive than depth – first solution

func movingCount_bfs(_ m: Int._ n: Int._ k: Int) -> Int {
    var visited = Array(repeating: Array(repeating: false, count: n), count: m)
    var result = 0
    var queue:Array = [(0.0.0.0)]

    while !queue.isEmpty {
        let (y,x,si,sj) = queue.removeFirst()
        if y > = m || x > = n || k < si + sj || visited[y][x]{
            continue
        }
        visited[y][x] = true
        result = result + 1
        queue.append((y + 1, x, digitSum(y + 1), sj))
        queue.append((y, x + 1, si, digitSum(x + 1)))}return result
}
Copy the code