0%

剑指Offer算法题-机器人的运动范围

Posted on In

题目

地上有一个 m 行 n 列的方格，一个机器人从坐标 $ (0,0) $的格子开始移动，它每次可以向左，右，上，下移动一格，但不能进入行坐标和列坐标的位数之和大于$k$的格子。例如，当 $k$为 18 时，机器人能够进入方格$(35,37)$,因为$3+5+3+7=18$。但它不能进入方格$(35,38)$。因为$3+5+3+8=19$。请问该机器人能够到达多少个格子？

思路

可以把方格看做一个$m \times n$的矩阵。在这个矩阵中，除边界以外的格子之外，其他格子都有四个相邻的格子。

  1. 机器人从坐标$ (0,0) $开始移动
  2. 当机器人准备进入到$ (i,j) $时，判断机器人能否进入到该格子
  3. 判断机器人是否能进入格子的条件是，行和列的位数之和小于 k，并且机器人也没有进入过次格子
  4. 若不能进入，则不去尝试进入到它周围的格子。
  5. 若能进入，则让机器人分别去尝试进入它周围的四个格子$ (i-1,j) , (i+1,j) , (i,j+1) , (i,j-1) ,$,而由于格子是从$ (0,0) $开始的，只需要向上和向右就能进入到所有能到达的格子，所以只需让机器人分别去尝试进入它上面或右面的格子 $(i+1,j) , (i,j+1) , $。也就是回到第 2 步。

代码实现（Swift）

首先用结构体Grid来表示 m 行 n 列的方格

1
//用来表示每个格子的坐标
2
typealias Coordinate = (row:Int,column:Int)
3
struct Grid {
4
    let row : Int //行数
5
    let column : Int //列数
6
    //原点坐标
7
    var originCoordinate : Coordinate {
8
        return (row:0,column:0)
9
    }
10
    //在方格内指定坐标的上面的格子，若上面已没有格子，则返回nil
11
    func above(coor:Coordinate) -> Coordinate? {
12
        if coor.row >= 0 && coor.row < row - 1 && coor.column >= 0 && coor.column < column{
13
            return (row:coor.row + 1,column:coor.column)
14
        }
15
        return nil
16
    }
17
    //在方格内指定坐标的下面的格子，若下面已没有格子，则返回nil
18
    func below(coor:Coordinate) -> Coordinate? {
19
        if coor.row > 0 && coor.row < row && coor.column >= 0 && coor.column < column{
20
            return (row:coor.row - 1,column:coor.column)
21
        }
22
        return nil
23
    }
24
    //在方格内指定坐标的左面的格子，若左面已没有格子，则返回nil
25
    func left(coor:Coordinate) -> Coordinate? {
26
        if coor.row >= 0 && coor.row < row && coor.column > 0 && coor.column < column{
27
            return (row:coor.row,column:coor.column - 1)
28
        }
29
        return nil
30
    }
31
    //在方格内指定坐标的右面的格子，若右面已没有格子，则返回nil
32
    func right(coor:Coordinate) -> Coordinate? {
33
        if coor.row >= 0 && coor.row < row && coor.column >= 0 && coor.column < column - 1{
34
            return (row:coor.row,column:coor.column + 1)
35
        }
36
        return nil
37
    }
38
}

然后在用结构体Robot来表示机器人

1
struct Robot {
2
    let k : Int
3
    let grid : Grid //格子
4
5
    init(k :Int, grid: Grid) {
6
        self.k = k
7
        self.grid = grid
8
    }
9
10
    //对外暴露的方法，做了一些数据的初始化和边界的判断。内部调用了private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int
11
    func movingCount() -> Int {
12
        guard k >= 0, grid.column > 0, grid.row > 0 else { return 0 }
13
        var visited = Array(repeating: false, count: grid.row * grid.column)
14
        let count = movingCount(coor: grid.originCoordinate , visited : &visited)
15
        return count
16
    }
17
18
    //实现上面的思路
19
    private func movingCount(coor:Coordinate? , visited:inout [Bool]) -> Int {
20
        if let coor = coor , isVaild(coor: coor, visited: visited) {
21
            visited[coor.row * grid.column + coor.column] = true
22
            return 1 + movingCount(coor:grid.above(coor: coor), visited: &visited)
23
                     + movingCount(coor:grid.right(coor: coor), visited: &visited)
24
        }
25
        return 0
26
    }
27
28
    //用来判断是否能进入到此格子
29
    private func isVaild(coor:Coordinate , visited : [Bool]) -> Bool {
30
        return visited[coor.row * grid.column + coor.column] == false && (digitsSum(number: coor.row) + digitsSum(number: coor.column) <= k)
31
    }
32
33
    //求一个数字的位数之和
34
    private func digitsSum(number:Int) -> Int {
35
        var sum = 0
36
        var topDigit = number
37
        while topDigit > 0 {
38
            sum += topDigit % 10
39
            topDigit = topDigit / 10
40
        }
41
        return sum
42
    }
43
}

Test

1
let grid = Grid(row: 100, column: 100)
2
for i in -2...30 {
3
    let robot = Robot(k: i, grid : grid)
4
    let count = robot.movingCount()
5
    print("\(i)===\(count)")
6
}