【刷算法】求機器人的運動范圍

AlphaWatch 發布于2019-08-22 18:40 / 3181人閱讀

摘要：一個機器人從坐標的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于的格子。例如，當為時，機器人能夠進入方格，因為。

題目描述

地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行坐標和列坐標的數位之和大于k的格子。例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

分析

對于每個到(x,y)的機器人，有四種移動可能，上下左右，即：(x+1,y)，(x-1,y)，(x,y-1)，(x,y+1)；

決定該位置是否合法要檢查這么幾個方面：

x、y坐標不能超出rows和cols的界限

x、y的坐標數位之和不能大于k

代碼實現

function movingCount(k, rows, cols)
{
    var flags = [];
    for(var i = 0;i < rows;i++) {
        flags.push([]);
        for(var j = 0;j < cols;j++) {
            flags[i].push(0);
        }
    }
    
    return steps(0,0,rows,cols,flags, k);
}
function steps(x, y, rows, cols, flags, k){
    if(x <0 || x >= rows || y < 0 || y >= cols || flags[x][y] === 1 || (bitSum(x) + bitSum(y) > k) )
        return 0;
    flags[x][y] = 1;
    return steps(x-1, y, rows, cols, flags, k) + steps(x+1, y, rows, cols, flags, k) + steps(x, y-1, rows, cols, flags, k) + steps(x, y+1, rows, cols, flags, k) + 1;
}

function bitSum(n){
    var sum = 0;
    while(n >= 1){
        sum += n%10;
        n = Math.floor(n/10);

    }
    return sum;
}

GPU云服務器云服務器機器學習的算法常用的機器學習算法 java算法求素數 webrtc復數求模快速算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/96065.html

為什么需要微積分

摘要：以解析幾何作為基礎，為微積分的研究創立開辟了道路，它用于研究數圖形運動以及變化。萊布尼茨創造的微積分符號更優秀，并沿用至今。推動人類進程，微積分是人類研究自然規律的基本工具，使人們對事物的認知有了飛躍。微積分我們知道數學是人類描述自然規律的語言將現實世界進行抽象，有了數學這個工具就能讓我們對物體數量、物體結構、物體的空間、物體的運動等進行抽象量化描述。現今的數學已經發展出很多分支，微積分也...

wushuiyong 2019-05-21 19:27 評論0 收藏0
SegmentFault 技術周刊 Vol.30 - 學習 Python 來做一些神奇好玩的事情吧

摘要：學習筆記七數學形態學關注的是圖像中的形狀，它提供了一些方法用于檢測形狀和改變形狀。學習筆記十一尺度不變特征變換，簡稱是圖像局部特征提取的現代方法基于區域圖像塊的分析。本文的目的是簡明扼要地說明的編碼機制，并給出一些建議。 showImg(https://segmentfault.com/img/bVRJbz?w=900&h=385); 前言開始之前，我們先來看這樣一個提問： pyth...

lifesimple 2019-07-30 14:22 評論0 收藏0