13.md

机器人的运动范围

题目

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

进阶：空间复杂度 O(nm)，时间复杂度 O(nm)

示例

输入：1,2,3 返回值：3

思路

• DFS遍历，详见注释

实现

func movingCount(threshold, rows, cols int) int {
	// 初始化做标记的矩阵
	flags := make([][]int, rows)
	for i := 0; i < rows; i++ {
		flags[i] = make([]int, cols)
	}
	// 烘托气氛
	var handler func(int, int) int
	handler = func(i, j int) int {
		// 边界检查
		if i < 0 || i >= rows || j < 0 || j >= cols {
			return 0
		}
		// 是否访问过
		if flags[i][j] != 0 {
			return 0
		}
		// 检查当前坐标是否满足条件
		if check(threshold, i, j) {
			return 0
		}
		// 标记访问过
		flags[i][j] = 1
		return 1 + handler(i-1, j) + handler(i+1, j) + handler(i, j-1) + handler(i, j+1)
	}
	return handler(0, 0)
}

func check(threshold, i, j int) bool {
	sum := 0
	for i > 0 {
		sum += i % 10 // 取个位数
		i = i / 10    // 移除个位
	}
	for j > 0 {
		sum += j % 10 // 取个位数
		j = j / 10    // 移除个位
	}
	return sum > threshold
}