Robot Movement Range

1. Problem Description

There is a grid with m rows and n columns. A robot starts at coordinate (0,0) and can move one cell at a time left, right, up, or down, but it cannot enter a cell when the sum of the digits of its row and column coordinates is greater than k. For example, when k is 18, the robot can enter (35,37) because 3+5+3+7 = 18, but it cannot enter (35,38) because 3+5+3+8 = 19. How many cells can the robot reach?

2. Approach

• Recursion

3. Implementation

package main

import "fmt"

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @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. References

• Robot Movement Range - NowCoder