How to solve the problem of robot walking on the grid in Java-javaTutorial-php.cn

How to solve the problem of robot walking on the grid in Java

WBOY

Release： 2023-04-24 09:28:12

forward

1243 people have browsed it

Title: There is a grid with m rows and n columns on the map. A robot starts to move from the grid of coordinates (0,0). The directions it can move each time are up, down, left, and right, and each time You can only move one grid, but you cannot enter a grid where the sum of row coordinates and column coordinates is greater than K. For example, when K is 16, the robot can enter square (24,19) because 2 4 1 9 = 16, but cannot enter square (34, 28) because 3 4 2 8 = 17>16,

Q: How many grids can this robot reach?

Analysis:

This question is relatively simple and can be broken down into 4 parts:

1) How to calculate the sum of the digits of a number

2) Whether the robot can enter a certain grid

3) If it can enter the grid, whether the grids in the four neighboring areas can enter,

4) Statistics can reach a total of multiple grids

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>

Copy after login

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>

Copy after login

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>

Copy after login

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

Copy after login

The above is the detailed content of How to solve the problem of robot walking on the grid in Java. For more information, please follow other related articles on the PHP Chinese website!