Backtracking algorithm - Range of motion of the robot

preface

You have a matrix where the robot can move from a grid at the coordinate (0,0), and it can move one grid to the left, one grid to the right, one grid to the top, one grid to the bottom, but it can’t enter a grid where the sum of the rows and columns is greater than K. Find out how many grids the robot can move from and its trajectory.

This article will share the solution to this problem and welcome interested developers to read this article.

Implementation approach

In the last article on finding paths in matrices, we learned to use backtracking to access a lattice in a matrix, and the problem we’re going to discuss here is to make a level of judgment before accessing a lattice. If the conditions are met, you get in, if not, you don’t get in.

The level of judgment we need to make is: calculate the sum of the digits of the coordinates of the lattice to be accessed, if it is greater than K (maximum active range), it cannot be accessed.

Sum of places: the result of taking the values of each position in a number and adding them up. For example, the sum of the digits in 19 is 1 + 9 = 10.

Determines whether the current cell is accessed

First, we need to create a matrix of the same size as the original matrix to identify whether the robot has walked the cell.

It is not possible to directly create a two-dimensional array of the specified size in js. The creation idea is as follows:

Creates an array with the size of the matrix
Iterate over the created array, then create an array with the size of array 0th of the matrix, and assign a value to each item traversed.

Determine whether the grid is accessible

When accessing the grid, we need to judge whether the grid to be accessed can be entered. We need to calculate the sum of the digits of the travel coordinate and the column coordinate, and then add them to judge whether the sum result is greater than the maximum range of motion (K) of the robot.

There are two ways to calculate the sum of the digits:

Turn the number into a string, walk through and take each character and turn it into a number and then add it up
Modulo operations are performed on numbers, the results are added, and the numbers themselves are performed/ 10Operation until the number is less than or equal to 0

Start moving the robot

For mobile robot, we need 7 parameters:

The total number of rows in the matrix
The total number of columns in a matrix
The coordinates of the rows that are going into the cell
The coordinates of the columns that are about to enter the cell
Maximum range of activity
Access identity matrix
Path matrix

First, we need to make boundary condition judgment (recursive termination condition). If the condition satisfies, it means that the grid is inaccessible, and the walkable grid is 0 (directly return 0) :

The row coordinates of the cell to be accessed are greater than the total number of rows of the matrix
The row coordinates of the cell to be accessed are less than 0
The column coordinates of the cell to be accessed are greater than the total number of columns of the matrix
The column coordinates of the cell to be accessed are less than 0
The current cell has been accessed
The current cell cannot be entered

If all the above conditions are met, it means that the current grid can be accessed, save the value in the current grid to the action trajectory, identify the current grid as the accessed state, the number of traveled grids +1, and recursively try whether the other four directions of the current grid can be accessed.

When the recursion stack is cleared, we have the total number of cells that the robot can enter and its trajectory.

The implementation code

Next, let’s translate this idea into TypeScript code.

Can the lattice enter the function

Let’s first look at the implementation of the function that determines whether the current grid can be entered, as follows:

  /** * Determine whether the robot can enter the target grid *@param Row Row coordinates *@param Col column coordinates *@param Target critical point *@private* /
  private checkPath(row: number.col: number.target: number) :boolean {
    // The sum of the digits of two coordinates must be less than or equal to the critical point
    return sumOfDigits(row) + sumOfDigits(col) <= target;
  }

// Turn the string implementation
export function sumOfDigits(target: number) :number {
  let finalVal = 0;
  const computeVal = target.toString();
  for (let i = 0; i < computeVal.length; i++) {
    finalVal += Number(computeVal[i]);
  }
  return finalVal;
}

// Sum of digits - modular operation implementation
export function sumOfDigitsForModular(target: number) :number {
  let finalVal = 0;
  while (target > 0) {
    finalVal += Math.floor(target % 10);
    target /= 10;
  }
  return finalVal;
}
Copy the code

Mobile robot function

Mobile robot to the specified grid implementation code is as follows:

  /** * Start mobile robot *@param Rows Total number of rows in the matrix *@param Total number of columns in colS matrix *@param Row Specifies the coordinate of the row to enter the cell@param Col column coordinates * to enter the grid@param Threshold Indicates the maximum active range *@param IsVisited Access identifier matrix *@param Matrix Path matrix *@private* /  
	private startMoving(
    rows: number.cols: number.row: number.col: number.threshold: number.isVisited: Array<Array<boolean>>,
    matrix: Array<Array<T>>
  ): number {
    // Boundary condition judgment
    if (
      row >= rows ||
      row < 0 ||
      col >= cols ||
      col < 0 ||
      isVisited[row][col] ||
      !this.checkPath(row, col, threshold)
    ) {
      return 0;
    }
    // Record the contents of the currently accessed grid
    this.path += `${matrix[row][col]}- > `;
    // Indicates that the current grid is accessed
    isVisited[row][col] = true;
    // Number of grid accesses +1
    return (
      1 +
      this.startMoving(rows, cols, row + 1, col, threshold, isVisited, matrix) +
      this.startMoving(rows, cols, row, col + 1, threshold, isVisited, matrix) +
      this.startMoving(rows, cols, row - 1, col, threshold, isVisited, matrix) +
      this.startMoving(rows, cols, row, col - 1, threshold, isVisited, matrix)
    );
  }
Copy the code

The main function

Finally, let’s look at the implementation of the main function, as follows:

  /** * Topic: * there is a square with m rows and n columns on the ground. * a robot starts moving from a cell at the coordinate (0,0). * it can move one cell at a time to the left, right, up, or down, but cannot enter a cell where the sum of the rows and column coordinates is greater than k. * for example, when k is 18, the robot can enter the square (35,37) because 3+5+3+7=18. * but it cannot enter the square (35,38) because 3+5+3+8=19. How many cells can the robot reach? *@param Matrix matrix *@param Threshold Threshold (maximum activity range) */
  public movingCount(matrix: Array<Array<T>>, threshold = 0) :number {
    if (threshold < 0 || matrix.length <= 0) {
      return 0;
    }
    // Get the total number of rows and columns of a square
    const rows = matrix.length;
    const cols = matrix[0].length;
    // Create a tag array that identifies whether the grid is accessed
    const isVisited: Array<Array<boolean> > =new Array(rows);
    for (let i = 0; i < isVisited.length; i++) {
      isVisited[i] = new Array(cols);
    }
    // count the total number of moving cells from position 0,0
    return this.startMoving(rows, cols, 0.0, threshold, isVisited, matrix);
  }
Copy the code

For the full code, go backtracking.ts #L80

Write test cases

Next, we construct a matrix to verify that the above code executes correctly, as follows:

const pathArr = [
  ["a"."b"."t"."g"],
  ["c"."f"."c"."s"],
  ["j"."d"."e"."h"]].const backtracking = new Backtracking<string>();
const totalCount = backtracking.movingCount(pathArr, 4);
const path = backtracking.path;
console.log(
  "The total number of cells the robot can walk is:",
  totalCount,
  ", the motion trajectory is:",
  path.substr(0, path.length - 3));Copy the code

The execution result is as follows:

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please go to my personal website to learn more.

Feel free to correct any mistakes in the comments section, and if this post helped you, feel free to like and follow 😊
This article was originally published in Nuggets and cannot be reproduced without permission at 💌

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Backtracking algorithm – Range of motion of the robot

preface

Implementation approach

Determines whether the current cell is accessed

Determine whether the grid is accessible

Start moving the robot

The implementation code

Can the lattice enter the function

Mobile robot function

The main function

Write test cases

Write in the last

Backtracking algorithm – Range of motion of the robot

preface

Implementation approach

Determines whether the current cell is accessed

Determine whether the grid is accessible

Start moving the robot

The implementation code

Can the lattice enter the function

Mobile robot function

The main function

Write test cases

Write in the last

Related Posts

This lightweight rapid development framework is a productivity tool

ES6 to ES5 with Babel

Algorithm diagram: sliding window maximum