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

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
	count := 0
	// 代表 4 个方向的移动
	dirs:=[][]int{{0,1},{0,-1},{1,0},{-1,0}}
	// 标记数组，也可以使用一维
    visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}
	// 递归+回溯（利用闭包）
	var backtracking func(int, int)
	backtracking = func(i, j int) {
	  	// 坐标合法性、是否已访问、坐标是否满足阈值
		if i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] || check(i, j, threshold) {
			return
		}
		// access
		visited[i][j] = true

        count++
		// 四个方向寻找合法坐标
		for _, dir := range dirs {
			x, y := i+dir[0], j+dir[1]
			backtracking(x, y)
		}
	}
	
    backtracking(0, 0)

	return count
}

func check(rows, cols, threshold int) bool {
	cnt := 0
	
    for rows > 0 {
        cnt += rows % 10
        rows = rows / 10
    }

    for cols > 0 {
        cnt += cols % 10
        cols = cols / 10
    }

	return cnt > threshold
}