Comment résoudre le problème du robot marchant sur la grille en Java

Titre : Il y a une grille avec m lignes et n colonnes sur la carte. Un robot commence à se déplacer à partir de la grille aux coordonnées (0,0). Les directions dans lesquelles il peut se déplacer à chaque fois sont le haut, le bas, la gauche et la droite. et il ne peut déplacer que Déplacer une grille, mais ne peut pas entrer dans une grille où la somme des coordonnées de ligne et des coordonnées de colonne est supérieure à K. Par exemple, lorsque K vaut 16, le robot peut entrer dans le carré (24,19) car 2+4+1+9=16, mais ne peut pas entrer dans le carré (34,28) car 3+4+2+8= 17>16. ,

Q : Combien de grilles ce robot peut-il atteindre ?

Analyse :

Cette question est relativement simple et peut être décomposée en 4 parties :

1) Comment calculer la somme des chiffres d'un nombre

2) Si le robot peut entrer dans une certaine grille

3 ) S'il peut entrer dans la grille, si la grille dans les quatre quartiers peut être saisie,

4) Les statistiques peuvent atteindre plusieurs grilles au total

1) Code

<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><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

<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) Code

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;}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!