Java怎麼解決機器人走格子問題

題目：地圖上有一個m行n列的方格，一個機器人從座標（0,0）的格子開始移動，它每一次可以移動的方向是上、下、左、右，且每次只能移動一格，但是不能進入行座標和列座標數位總和大於K的格子。例子，當K為16時，機器人能夠進入方格（24,19），因為2 4 1 9=16，但是不能進入方格（34,28）,因為3 4 2 8=17>16,

問：該機器人能夠達到多少個格子。

分析：

這個題目比較簡單，可以把問題分解成4個部分：

1）如何計算數字的位數總和

# 2）機器人是否能夠進入某個格子

3） 如果能進入格子，四鄰域內的格子是否能夠進入，

4）統計一共能夠達到多個格子

1）代碼

<code>//计算数字位数之和</code><code>int getDigitSum(int number)</code><code>{</code><code><br></code><code>    int sum=0;//临时变量,保存一个数字数位和</code><code>    </code><code>    while(number){</code><code>        </code><code>        sum+=number%10;</code><code>        number/=10;</code><code>    }    </code><code><br></code><code>    return sum;</code><code><br></code><code>}</code>

2）代碼

<code>//机器人能否进入某个格子，即从三个方面考虑：</code><code>//①是否越界，②数位之和是否满足条件，③邻域格子是否已经访问过</code><code>bool check（int threshold,int rows,int cols,int row,int col,bool* visit）{</code><code><br></code><code>    if(row>=0&&col>=0&&row<rows&&col<cols&&getDigitSum(row)+getDigitSum(col)<=threshold)</code><code>        &&!visit[row*cols+col])</code><code>        return true;</code><code>    return false;</code><code><br></code><code>}</code>

3）代碼

<code>int movingCountCore(int threshold,int rows,int cols, int row,int col, bool *visited)</code><code>{</code><code><br></code><code>    int count=0;</code><code>    if(check(threshold,rows,cols,row,col,bool* visited))</code><code>        {</code><code><br></code><code>            visited[row*cols+col]=true;</code><code>            count+=1+movingCountCore(threshold,rows,cols,row-1,col,visited)</code><code>                 +movingCountCore(threshold,rows,cols,row+1,col,visited)</code><code>                 +movingCountCore(threshold,rows,cols,row,col-1,visited)</code><code>                 +movingCountCore(threshold,rows,cols,row,col+1,visited);</code><code>        }</code><code>    return count;</code><code><br></code><code>}</code>

4）程式碼

int movingCount(int threshold,int rows,int cols){    //要考虑负值的情况    if(threshold<0||rows<=0||cols<=0)        {return 0;}        bool* visited=new bool[rows*cols];    for(int i=0;i<=rows*cols;++i){        visited=false;    }    int count=movingCountCore(threshold,rows,cols,0,0,visited);    delete[] visited;    return count;}

以上是Java怎麼解決機器人走格子問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！