机器人的运动范围

1. 题目描述

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

2. 思路

• 递归

3. 实现

package main

import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param threshold int整型
 * @param rows int整型
 * @param cols int整型
 * @return int整型
 */

var visited = make(map[string]bool, 0)

func movingCount(threshold int, rows int, cols int) int {
	visited = make(map[string]bool, 0)
	return movingCount2(threshold, rows, cols, 0, 0)
}

func movingCount2(threshold int, rows int, cols int, currentRow int, currentCol int) int {
	if reachBoundary(rows, cols, currentRow, currentCol) {
		return 0
	}
	if sumExceedThreshold(threshold, currentRow, currentCol) {
		return 0
	}

	key := getKey(currentRow, currentCol)

	_, ok := visited[key]
	if ok {
		return 0
	}
	visited[key] = true
	return 1 + movingCount2(threshold, rows, cols, currentRow-1, currentCol) +
		movingCount2(threshold, rows, cols, currentRow+1, currentCol) +
		movingCount2(threshold, rows, cols, currentRow, currentCol-1) +
		movingCount2(threshold, rows, cols, currentRow, currentCol+1)
}

func getKey(currentRow int, currentCol int) string {
	return fmt.Sprintf("%v_%v", currentRow, currentCol)
}

func sumExceedThreshold(threshold int, currentRow int, currentCol int) bool {
	rowSum := 0
	for currentRow != 0 {
		rowSum += currentRow % 10
		currentRow /= 10
	}
	colSum := 0
	for currentCol != 0 {
		colSum += currentCol % 10
		currentCol /= 10
	}
	return rowSum+colSum > threshold
}

func reachBoundary(rows int, cols int, currentRow int, currentCol int) bool {
	if currentRow < 0 || currentCol < 0 || currentRow > rows-1 || currentCol > cols-1 {
		return true
	}

	return false
}

4. 参考

• 机器人的运动范围_牛客题霸_牛客网