剑指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

同面试题12一样，我们借助回溯法，借助一个O(MN)的内存空间存放一个访问二维数组，暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回 。

class Solution {
    func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
        // 构建一个为访问的二维数组
        var visited = Array(repeating: Array(repeating: false, count: n), count: m)
        // 从0 ，0 开始访问数组
        return movingCountCore(&visited, m, n, 0, 0,k);
    }
    
    func movingCountCore(_ visited: inout Array<Array<Bool>>,_ m: Int,_ n:Int, _ row :Int,_ column: Int, _ k: Int)->Int {
        var count = 0
     // DFS递归实现 访问值累加
        if check(&visited, m, n, row, column,k) {
            count = 1 + movingCountCore(&visited,m,n,row - 1,column, k) + movingCountCore(&visited,m,n,row+1,column, k) + movingCountCore(&visited,m,n,row,column-1, k) + movingCountCore(&visited,m,n,row,column+1, k)
        }
        return count
    }
    
  // 判断访问下标是否 数组越界、已访问、下标超过限制K
    func check(_ visited: inout Array<Array<Bool>>,_ m: Int,_ n:Int,_ row:Int, _ column:Int, _ k: Int)->Bool {
        if row < 0 || row >= m || column < 0 ||  column >= n || visited[row][column] != false || (getDigitNum(row) + getDigitNum(column)) > k{
            return false
        }
        visited[row][column] = true
        return true
    }
    // 计算数位之和
    func getDigitNum(_ number: Int) -> Int {
        var number = number
        var sum = 0
        while number > 0 {
            sum += number % 10
            number = number/10
        }
        return sum
    }
}