题解 | #机器人的运动范围#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param threshold int整型 
 * @param rows int整型 
 * @param cols int整型 
 * @return int整型
*/
func calSum(num int) int {
    sum := 0
    for num != 0 {
        sum += num % 10
        num = num / 10
    }
    return sum
}
func backtracking(threshold int, rows int, cols int, i int, j int, mark [][]int) int {
    count := 0
    if check(rows, cols, i, j, mark, threshold) {
        mark[i][j] = 1
        count = 1 + backtracking(threshold, rows, cols, i + 1, j, mark) + 
        backtracking(threshold, rows, cols, i - 1, j, mark) + 
        backtracking(threshold, rows, cols, i, j + 1, mark) +
        backtracking(threshold, rows, cols, i, j - 1, mark)
    }
    return count
}
func check(rows int, cols int, i int, j int, mark [][]int, threshold int) bool {
    if i < 0 || j < 0 || i >= rows || j >= cols {
        return false
    } else if mark[i][j] == 1 {
        return false
    } else if calSum(i) + calSum(j) > threshold {
        return false
    } else {
        return true
    }
}
func movingCount( threshold int ,  rows int ,  cols int ) int {
    // write code here
    mark := make([][]int, rows)
    for i, _ := range mark {
        mark[i] = make([]int, cols)
    }
    return backtracking(threshold, rows, cols, 0, 0, mark)
}