首页 > 试题广场 >

机器人的运动范围

[编程题]机器人的运动范围

热度指数：463200 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

地上有一个 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 。请问该机器人能够达到多少个格子？

数据范围： $0 \le threshold \le 15 \$ ， $1 \le rows,cols \le 100 \$

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

示例1

输入

1,2,3

输出

示例2

输入

0,1,3

输出

示例3

输入

10,1,100

输出

说明

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

示例4

输入

5,10,10

输出

算法知识视频讲解

推荐

lizo

public class Solution {

	public int movingCount(int threshold, int rows, int cols) {
		int flag[][] = new int[rows][cols]; //记录是否已经走过
		return helper(0, 0, rows, cols, flag, threshold);
	}

	private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) {
		if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;		
		flag[i][j] = 1;
		return helper(i - 1, j, rows, cols, flag, threshold)
            + helper(i + 1, j, rows, cols, flag, threshold)
			+ helper(i, j - 1, rows, cols, flag, threshold) 
            + helper(i, j + 1, rows, cols, flag, threshold) 
            + 1;
	}

	private int numSum(int i) {
		int sum = 0;
		do{
			sum += i%10;
		}while((i = i/10) > 0);
		return sum;
	}
}

编辑于 2021-07-06 10:49:06 回复(81)

JavaScript

NPC201904301802722

function movingCount(threshold, rows, cols)
{
    let canMove=(row,col)=>{
        if(row<0 || row>=rows || col<0 || col>=cols ){
            return false
        }
        if(Math.floor(row/10)+row%10 +Math.floor(col/10) +col%10 >threshold){
            return false
        }
        return true
    }
    
    let visitedArr=[]
    let getVisited=(row,col)=>{
        return visitedArr[row] && visitedArr[row][col]
    }
    let setVisited=(row,col)=>{
        if(!visitedArr[row]){
            visitedArr[row]=[]
        }
        visitedArr[row][col]=true
    }
    
    let move=(row,col)=>{
        if(!canMove(row,col)){
            return 0
        }
        if(getVisited(row,col)){
            return 0
        }
        setVisited(row,col)
        return 1+move(row-1,col)+move(row+1,col)+move(row,col+1)+move(row,col-1)
    }
    
    return move(0,0)
}

类似战棋游戏中移动范围的算法

发表于 2021-06-16 23:22:14 回复(0)

JavaScript

阿里巴巴天猫技术_急招

js下需要留意，getDigitNum函数中，num /= 10是无法得到正确结果的，因为js会将其除为小数，故应使用num = parseInt(num / 10)

发表于 2019-03-03 11:07:24 回复(0)

JavaScript

Jarsen

function movingCount(threshold, rows, cols)
{
let flag = []
for(let i=0;i <rows; i++){
flag.push([])
}
return helper(threshold, rows, cols, 0, 0, flag)
}
function helper(threshold, rows, cols, i, j, flag){
if(i<0 || i>=rows || j<0 || j>=cols || flag[i][j] || (bitAdder(i)+ bitAdder(j)) > threshold){
return 0
}
flag[i][j] = true
return 1 + helper(threshold, rows, cols, i+1, j, flag) +
helper(threshold, rows, cols, i-1, j, flag) +
helper(threshold, rows, cols, i, j+1, flag) +
helper(threshold, rows, cols, i, j-1, flag)
}
function bitAdder(n){
// n
let result = 0
while(n!=0){
result += n%10
// 注意n/10为浮点数，要进行转化
n = Math.floor(n/10)
}
return result
}

发表于 2019-02-19 17:37:31 回复(0)

JavaScript

执鸢者

//递归的方式
function movingCount(threshold, rows, cols)
{
    // write code here
    if(threshold < 0 || rows < 0 || cols < 0) {
        return 0;
    }
    
    let flagArr = (new Array(rows * cols)).fill(0);
    //从（0，0）开始
    let count = movingCountCore(threshold, rows, cols, 0, 0, flagArr);
    
    return count;
}

function movingCountCore(threshold, rows, cols, row, col, flagArr) {
    let count = 0;
    //首先检查是否符合该条件，如果符合返回true，不符合返回false
    if(check(threshold,rows, cols, row, col, flagArr)){
        //改变是否遍历过的标志位
        flagArr[row * cols + col] = 1;
        //利用递归的方式得到其总的数量
        count = 1 + 
            movingCountCore(threshold, rows, cols, row + 1, col, flagArr)+
            movingCountCore(threshold, rows, cols, row - 1, col, flagArr)+
            movingCountCore(threshold, rows, cols, row, col + 1, flagArr)+
            movingCountCore(threshold, rows, cols, row, col - 1, flagArr);
    }
    return count;
}

function check(threshold,rows, cols, row, col, flagArr) {
    if(row >= 0 && row < rows && col < cols && col >= 0 && getDigitSum(row) + getDigitSum(col) <= threshold && !flagArr[cols * row + col]){
       return true;
    }
    return false;
}

function getDigitSum(number) {
    let sum = 0;
    while(number > 0) {
        sum += number % 10;
        number = Math.floor(number / 10);
    }
    return sum;
}

//运用了循环的方式
function movingCount(threshold, rows, cols){
    if(threshold < 0 || rows < 0 || cols < 0) {
        return 0;
    }
    
    let flagArr = (new Array(rows * cols)).fill(0);
    
    let pushArr = [];
    let count = 0;
    if(check(threshold, rows, cols, 0 , 0, flagArr)) {
        pushArr.push([0,0]);
        flagArr[0] = 1;
    }
    while(pushArr.length > 0) {
        let outputArr = pushArr.pop();
        let row = outputArr[0];
        let col = outputArr[1];
        count++;
        if(check(threshold, rows, cols, row + 1, col, flagArr)){
            pushArr.push([row + 1,col]);
            flagArr[(row + 1) * cols + col] = 1;
        }
        if(check(threshold, rows, cols, row - 1, col, flagArr)){
            pushArr.push([row - 1,col]);
            flagArr[(row - 1) * cols + col] = 1;
        }
        if(check(threshold, rows, cols, row, col + 1, flagArr)){
            pushArr.push([row ,col + 1]);
            flagArr[row * cols + col + 1] = 1;
        }
        if(check(threshold, rows, cols, row , col - 1, flagArr)){
            pushArr.push([row ,col - 1]);
            flagArr[row * cols + col - 1] = 1;
        }
    }
    return count;
}
function check(threshold, rows, cols, row, col, flagArr) {
    if(row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !flagArr[row * cols + col]){
        return true;
    }
    return false;
}
function getDigitSum(number) {
    let sum = 0;
    while(number > 0) {
        sum += number % 10;
        number = Math.floor(number / 10);
    }
    return sum;
}

发表于 2019-01-11 21:08:10 回复(0)

JavaScript

汕大小吴

function movingCount(threshold, rows, cols)
{
    let visited = [];
    for(let i = 0; i< rows; i++){
        visited.push([]);
        for(let j = 0; j < cols; j++){
            visited[i][j] = false;
        }
    }
    return move(0, 0, rows, cols, visited, threshold);

}
function move(i, j, rows, cols, visited, threshold){
    if(i < 0 || i == rows || j < 0 || j == cols || visited[i][j]){
        return 0;
    }
    let sum = 0;
    let tmp = i + "" + j;
    for(let k = 0; k < tmp.length; k++){
        sum += tmp.charAt(k)/1;//转成数字
    }
    if(sum > threshold){
        return 0;
    }
    visited[i][j] = true;
    return 1 + move(i + 1, j, rows, cols, visited, threshold)
        + move(i, j + 1, rows, cols, visited, threshold)
        + move(i - 1, j, rows, cols, visited, threshold)
        + move(i, j - 1, rows, cols, visited, threshold);
}

发表于 2018-08-31 01:22:59 回复(0)

JavaScript

做时间的兄弟

function movingCount(threshold, rows, cols)
{
    // write code here
    var path = [];
    for (var i = 0; i < rows; i++) {
        path[i] = [];
        for (var j = 0; j < cols; j++) {
            if (getNum(i) + getNum(j) > threshold) {
                path[i][j] = 1;
            }else {
                path[i][j] = 0;
            }
        }
    }
    var doMoving = function (i,j,step) {
        if (i >= rows || i < 0 || j >= cols || j < 0) {
            return 0;
        }
        if (path[i][j] === 1) {
            return 0;
        }
        path[i][j] = 1;
        return doMoving(i+1,j) + doMoving(i,j+1) + doMoving(i-1,j) + doMoving(i,j-1) + 1;
    }
    return doMoving(0,0,0);
}

function getNum(num)  {
    var array = String(num).split('');
    var sum = 0;
    array.forEach(function(item){
        sum+=parseInt(item);
    });
    return sum;
}

发表于 2018-04-11 12:54:25 回复(0)

JavaScript

asdasdasd_

function movingCount(threshold, rows, cols)
{
    // write code here
    if(!threshold)return 1;
    if(!rows||!cols)return 0;
    var visited = [];
    var temp = [];
    var i, j;
    var count = {count:0};
    for (i = 0; i < rows; i++) {
      temp = [];
      for (j = 0; j < cols; j++) {
        temp.push(false);
      }
      visited.push(temp);
    }
    move(threshold, rows, cols, 0, 0, count, visited);
    return count.count;
}

function move(threshold, rows, cols, row, col, count, visited) {
    var isMove = false;
    if(rows>row&&cols>col&&col>=0&&row>=0&&!visited[row][col]) {
       if(bitSum(row) + bitSum(col) <= threshold) {
           visited[row][col] = true;
           count.count++;
           move(threshold, rows, cols, row+1, col, count, visited);
           move(threshold, rows, cols, row-1, col, count, visited);
           move(threshold, rows, cols, row, col-1, count, visited);
           move(threshold, rows, cols, row, col+1, count, visited);
       }
    }
    return isMove;
}

function bitSum(num) {
    var sum = 0;
    while(num) {
        sum+=num%10;
        num = parseInt(num/10)
    }
    return sum;
}

module.exports = {
    movingCount : movingCount
};

发表于 2017-08-29 12:41:03 回复(3)

提交观点

问题信息

递归

难度：

7条回答 1682收藏 110203浏览

通过挑战的用户

查看代码

等一个offe...

2022-10-13 10:02:36
lkjs

2022-09-23 14:40:48
真的会谢的芝士...

2022-09-16 07:37:17
快乐小神仙耶耶耶

2022-09-15 21:19:42
喜欢后撤步的四...

2022-09-15 19:51:53

机器人的运动范围

输入

输出

输入

输出

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题