Javaでロボットがグリッド上を歩く問題を解決する方法

タイトル: 地図上に m 行 n 列のグリッドがあり、ロボットは座標 (0,0) のグリッドから移動を開始します。一度に移動できる方向は上下左右です。移動できるグリッドは 1 つだけですが、行座標と列座標の合計が K より大きいグリッドには入力できません。たとえば、K が 16 の場合、ロボットは 2 4 1 9 = 16 であるため四角形 (24,19) に入ることができますが、3 4 2 8 = 17>16,

## であるため四角形 (34, 28) に入ることができません。 #Q: このロボットは何グリッドまで到達できますか?

分析:

この質問は比較的単純で、4 つの部分に分けることができます:

1) 数値の桁の合計を計算する方法

2) ロボットが特定のグリッドに入ることができるかどうか

3) ロボットがグリッドに入ることができる場合、隣接する 4 つのエリアのグリッドが入ることができるかどうか、

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 中国語 Web サイトの他の関連記事を参照してください。