“This is the 29th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

13. Range of motion of robot

The title

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: 3Copy the code

Example 2

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

prompt

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

Answer key

Wrong answer key

Here is the author’s first impression of the wrong way of thinking, readers need not read this paragraph.

  • It can move left, right, up and down one space at a time. It doesn’t say it can’t go back
  • Can not enter the row and column coordinates of the sum of the number of digits is greater than k, statistics a down coordinates and column coordinates of the sum of the number of digits is less than or equal to k lattice soon finished? Why is this so hard?

The code is as follows:

var movingCount = function (m, n, k) {
  let result = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const t = heler(i) + heler(j);
      if(t <= k) result++; }}return result;

  function helper(x) {
    let num = 0;
    while (x >= 1) {
      num += x % 10;
      x = Math.floor(x / 10);
    }
    returnnum; }};Copy the code

It doesn’t feel like a problem. Edit, execute, submit; Pass test case 2/49

I’m afraid I’m an idiot. Check what’s wrong?

y\x 0 1 2 3 4 5 6
0 0 1 2 3 4
5 \color{blue}{5} 		6
1 1 2 3 4
5 \color{blue}{5} 		6 7
2 2 3 4
5 \color{blue}{5} 		6 7 8
3 3 4
5 \color{blue}{5} 		6 7 8 9
4 4
5 \color{blue}{5} 		6 7 8 9
5
5 \color{blue}{5} 		6 7 8 9
6 6 7 8 9
7 7 8 9
8 8 9 1
9 9 1 2
10 1 2 3
11 2 3 4

The robot starts from [0,0][0,0][0,0] and is blocked by the middle blue 5\color{blue}{5}5. It cannot go to [0,10][0,10]. Although [0,10][0,10][0,10] the sum of the digits of the row and column coordinates is less than KKK

Problem found, return to the correct solution idea: DFS

Correct problem solving DFS

DFS pseudo code

var movingCount = function (m, n, k) {
    // the robot starts from position [0,0]
     dfs(0.0)
     function dfs(i,j){
         // I represents the coordinates of the row where the robot is located
         // j represents the robot sitting in the column coordinates
         
         // The sum of the digits of row and column coordinates is greater than k terminates recursion
         if( helper(i) + helper(j)  > k) return;
         
         // I,j out of bounds, terminates recursion
         if(i < 0 || i >= m || j < 0 || j >=n) return
         
         dfs(i+1,j);
         dfs(i-1,j);
         dfs(i,j-1);
         dfs(i,j+1); }};Copy the code

So what’s the use of helperHelperHelper?

Helperhelper converts integers to digits as follows:

function helper(x) {
    let num = 0;
    while (x >= 1) {
      num += x % 10;
      x = Math.floor(x / 10);
    }
    return num;
  }
Copy the code

According to the above DFS idea, edit the code as follows:

The complete code

var movingCount = function (m, n, k) {
  let result = 0;
  let array = Array(m);
  for (let i = 0; i < m; i++) {
    array[i] = Array(n).fill(0);
  }
  dfs(0.0, k);
  return result;
  function dfs(i, j, k) {
    if (
      i >= 0 &&
      j >= 0&& i < m && j < n && array[i][j] ! = =1 &&
      helper(i) + helper(j) <= k
    ) {
      result++;
      const low = [-1.1.0.0];
      const row = [0.0, -1.1];
      array[i][j] = 1;
      for (let s = 0; s < 4; s++) {
        const x = i + low[s];
        consty = j + row[s]; dfs(x, y, k); }}}function helper(x) {
    let num = 0;
    while (x >= 1) {
      num += x % 10;
      x = Math.floor(x / 10);
    }
    returnnum; }};Copy the code