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 codeMobile 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 codeThe 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 codeFor 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 codeThe 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 💌