Topic link

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: 3

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

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

Answer key

You can think of the grid as an m by nm times nm by n matrix. In this matrix, every cell except the one on the boundary has four adjacent cells.

  1. The robot moves from coordinates (0,0)(0,0)(0,0)
  2. When the robot is ready to enter (I,j)(I,j)(I,j), judge whether the robot can enter the grid
  3. The condition to judge whether a robot can enter a cell is that the sum of the number of rows and columns is less than K, and the robot has never entered a second cell
  4. If not, do not attempt to enter the surrounding grid.
  5. If I can get in, Let robot, respectively, to try to enter it around four grid (I – 1, j), (I + 1, j), (I, j + 1), (I, j – 1), (I – 1, j), (I + 1, j), (I, j + 1), (I, j – 1), (I – 1, j), (I + 1, j), (I, j + 1), (I, j – 1), and the grid from (0, 0) (0, 0) (0, 0), only need to up and to the right can enter all can reach to the grid, So just let robot respectively, or to try to enter it right grid (I + 1, j), (I, j + 1), (I + 1, j), (I, j + 1), (I + 1, j), (I, j + 1). So let’s go back to step 2.

code

First, the structure Grid is used to represent the Grid of m rows and N columns

Typealias Coordinate = (row:Int,column:Int) struct Grid {let row:Int Var originCoordinate: Coordinate {return (row:0,column:0)} nil func above(coor:Coordinate) -> Coordinate? { if coor.row >= 0 && coor.row < row - 1 && coor.column >= 0 && coor.column < column{ return (row:coor.row + 1,column:coor.column)} return nil func below(coor:Coordinate) -> Coordinate? { if coor.row > 0 && coor.row < row && coor.column >= 0 && coor.column < column{ return (row:coor.row - 1,column:coor.column)} return nil func left(coor:Coordinate) -> Coordinate? { if coor.row >= 0 && coor.row < row && coor.column > 0 && coor.column < column{ return (row:coor.row,column:coor.column - 1)} return nil func right(coor:Coordinate) -> Coordinate? { if coor.row >= 0 && coor.row < row && coor.column >= 0 && coor.column < column - 1{ return (row:coor.row,column:coor.column + 1) } return nil } }Copy the code

And then we use the structure Robot to represent the Robot

Struct Robot {let k :Int let grid: grid // Grid) {self.k = k self. Grid = Grid} Internal call to private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int func movingCount() -> Int { guard k >= 0, grid.column > 0, grid.row > 0 else { return 0 } var visited = Array(repeating: false, count: grid.row * grid.column) let count = movingCount(coor: grid.originCoordinate , visited : &visited) return count} private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int { if let coor = coor , isVaild(coor: coor, visited: visited) { visited[coor.row * grid.column + coor.column] = true return 1 + movingCount(coor:grid.above(coor: coor), visited: &visited) + movingCount(coor:grid.right(coor: coor), visited: &visited)} return 0} private func isVaild(Coor :Coordinate, visited: [Bool]) -> Bool { return visited[coor.row * grid.column + coor.column] == false && (digitsSum(number: coor.row) + digitsSum(number: Column) <= k)} private func digitsSum(number:Int) -> Int {var sum = 0 var topDigit = number while private func digitsSum(number:Int) -> Int {var sum = 0 var topDigit = number while topDigit > 0 { sum += topDigit % 10 topDigit = topDigit / 10 } return sum } }Copy the code