This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Topic describes

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
  • Tip:
`1 <= n,m <= 100`
`0 <= k <= 20`
Copy the code

Implementation approach

We can solve this problem by using breadth-first traversal (BFS) and depth-first traversal (DFS). To prevent backtracking, we define an array array to record whether or not we entered the cell.

  • Breadth-first traversal

Define a dlist array to represent the direction of the mobile grid (up and down or so) to define res said into the grid number, use the queque queue first-in, first-out principle push the up and down or so of each grid were taken out from the head to determine whether out of box, before entering, coordinate grid digital is greater than the sum of k, the final statistical res.

/ * * *@param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}* /
var movingCount = function(m, n, k) {
    let res = 0
    let array = new Array(m).fill(0).map(() = > new Array(n).fill(false));
    let dlist = [
        [0.1],
        [0, -1],
        [1.0], [...1.0]]let queue = [[0.0]]
    while (queue.length) {
        let [i, j] = queue.shift()
        let num = getNum(i) + getNum(j)
        if (i < 0 || i >= m || j < 0 || j >= n  || num > k || array[i][j]) continue
        array[i][j] = true
        ++res
        for (let item of dlist) {
           queue.push([item[0] + i, item[1] + j])
        }
    }
    return res
};
function getNum(number) {
    if (number == 100) return 1
    return parseInt(number / 10) + number % 10
}
Copy the code
  • Depth-first traversal

The callback DFS is used to represent the upper, lower and lower sides of each grid, which does not meet the judgment condition return. Finally, the number of entered grids (RES) is calculated.

/ * * *@param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}* /
var movingCount = function(m, n, k) {
    let res = 0
    let array = new Array(m).fill(0).map(() = > new Array(n).fill(false));
    let dfs = function (i, j) {
        let num = getNum(i) + getNum(j)
        if (i < 0 || i >= m || j < 0 || j >= n  || num > k || array[i][j]) return
        array[i][j] = true
        ++res
        dfs(i, j - 1)
        dfs(i, j + 1)
        dfs(i - 1, j)
        dfs(i + 1, j)  
    }
    dfs(0.0)
    return res
};
function getNum(number) {
    if (number == 100) return 1
    return parseInt(number / 10) + number % 10
}
Copy the code