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

题目

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

思路

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

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

代码实现（Swift）

首先用结构体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
    }
}

Test

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