LeetCode-剑指 Offer 13. 机器人的运动范围

题目链接

题目描述

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

示例 1：
输入：m = 2, n = 3, k = 1
输出：3

示例 2：
输入：m = 3, n = 1, k = 0
输出：1

提示：
1 <= n,m <= 100
0 <= k <= 20

题解

可以把方格看做一个$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步。

代码

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

//用来表示每个格子的坐标
typealias Coordinate = (row:Int,column:Int)
struct Grid {
    let row : Int //行数
    let column : 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
    }
    //在方格内指定坐标的下面的格子，若下面已没有格子，则返回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
    }
    //在方格内指定坐标的左面的格子，若左面已没有格子，则返回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
    }
    //在方格内指定坐标的右面的格子，若右面已没有格子，则返回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
    }
}
复制代码

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

struct Robot {
    let k : Int
    let grid : Grid //格子
  
    init(k :Int, grid: Grid) {
        self.k = k
        self.grid = grid
    }
    
    //对外暴露的方法，做了一些数据的初始化和边界的判断。内部调用了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: coor.column) <= k)
    }
    
    //求一个数字的位数之和
    private func digitsSum(number:Int) -> Int {
        var sum = 0
        var topDigit = number
        while topDigit > 0 {
            sum += topDigit % 10
            topDigit = topDigit / 10
        }
        return sum
    }
}
复制代码