This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The range of motion of the robot

There is a square with m rows and n columns on the ground, from coordinates [0,0] to coordinates [m-1,n-1]. A robot starts at the grid [0, 0] and can move left, right, up, or down one at a time (not to square). It cannot enter a grid where the sum of the row and column coordinates 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 square [35, 38] because 3+5+3+8=19. How many grids can the robot reach?

 

Example 1:

Input: m = 2, n = 3, k = 1 Output: 3

Input: m = 3, n = 1, k = 0 output: 1

1 <= n,m <= 100 0 <= k <= 20

Answer key

Method 1: Depth-first traversal – Java

This question is of the same type as yesterday’s question.

Depth-first search: it can be understood as a violent method to simulate all paths of the robot in the matrix. DFS recursively searches to the end in one direction, goes back to the last node, searches in another direction, and so on.

Pruning: In a search, if the element has been accessed by digits and beyond the target value, it should be returned immediately, called feasible pruning.

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return movingCountHelp(0.0, k, visited);
    }

    private int movingCountHelp(int i, int j, int k, boolean[][] visited) {
        int sum = movingCountSum(i) + movingCountSum(j);
        if (i >= visited.length || j >= visited[0].length ||
                sum > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + movingCountHelp(i + 1, j, k, visited) + movingCountHelp(i, j + 1, k, visited);
    }

    private int movingCountSum(int num) {
        int sum = 0;
        while(num ! =0) {
            sum += num % 10;
            num /= 10;
        }
        returnsum; }}Copy the code

Time complexity: O (MN)

Space complexity: O (MN)

Method 1: Depth-first traversal — Go

func movingCount(m int, n int, k int) int {
    vis := make([] []bool, m)
    for i, _ := range vis {
        vis[i] = make([]bool, n)
    }
    return dfs(0.0, m, n, k, vis)
}

func dfs(i, j, m, n, k int, vis [][]bool) int {
    if i<0 || i>=m || j<0 || j>=n || (i/10+i%10+j/10+j%10) > k || vis[i][j] {
        return 0
    }
    vis[i][j] = true
    return dfs(i+1, j, m, n, k, vis) + dfs(i- 1, j, m, n, k, vis) +
            dfs(i, j+1, m, n, k, vis) + dfs(i, j- 1, m, n, k, vis) + 1
}
Copy the code

Method 2: Width first traversal – Java

We regard the grid with the sum of row and column coordinates digits greater than K as an obstacle, so this problem is a very traditional search topic. We can use breadth-first search or depth-first search to solve it, and this paper chooses breadth-first search to explain it.

So how do you add up the digits of a number? We just need to know what the units digit of x is every time we mod 10 logarithm x, and then divide x by 10. This operation is equivalent to moving the decimal number of X to the right by one digit, removing the units digit (similar to the >> right shift operator in binary), and repeating until x is 0.

There is also a hidden optimization to this problem:

Instead of searching up and left, our search direction can be reduced to right and down. The value in each grid is the sum of the digits of row and column coordinates. The blue square represents the non-obstacle square, that is, its value is less than or equal to the current limit k.

It can be found that as the limiting condition k increases, the newly added non-obstacle squares in the blue square region where (0, 0) is located can be obtained by moving the upper or left squares by one step. Other disconnected blue squares will be connected with the increase of K, and when connected, they are also obtained by moving the upper or left squares one step, so we can reduce our search direction to right or down.

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue= new LinkedList<int[] > (); queue.add(new int[] { 0.0.0.0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10! =0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10! =0 ? sj + 1 : sj - 8 });
        }
        returnres; }}Copy the code