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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param threshold int整型 
 * @param rows int整型 
 * @param cols int整型 
 * @return int整型
*/
func movingCount( threshold int ,  rows int ,  cols int ) int {
    // write code here
    var ans int
    var visted = make([][]bool, rows)
    for i := range visted {
        visted[i] = make([]bool, cols)
    }

    ways := [][]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}

	var overBoard = func(i, j int) bool {
		return i < 0 || i >= rows || j < 0 || j >= cols
	}

    var sumOfDit func(num int) int
    sumOfDit = func(num int) int {
        sum := 0
        for num != 0 {
            digit := num % 10    // 取得最低位的数字
            sum += digit         // 将数字加到总和上
            num /= 10            // 去掉最低位
        }
        return sum
    }

    var dfs func(i, j int) 
    dfs = func(i, j int) {
        // 1. 满足条件， 记录
        if (sumOfDit(i) + sumOfDit(j)) <= threshold && !visted[i][j] {
            ans++
            visted[i][j] = true
        } else {
            // 2. 终止
            return
        }
      
        // 继续搜索

        for _, w := range ways {
            ni := i + w[0]
            nj := j + w[1]

            if overBoard(ni, nj) { continue }
            if visted[ni][nj] { continue }
             
             dfs(ni, nj)

        }

    }

    dfs(0, 0)

    return ans
}