Titel: Auf der Karte befindet sich ein Gitter mit m Zeilen und n Spalten. Ein Roboter beginnt sich ausgehend vom Koordinatengitter (0,0) zu bewegen. und rechts, und jedes Mal können Sie jeweils nur ein Gitter verschieben, aber Sie können kein Gitter eingeben, bei dem die Summe der Zeilenkoordinaten und Spaltenkoordinaten größer als K ist. Wenn K beispielsweise 16 ist, kann der Roboter das Quadrat (24,19) eingeben, weil 2+4+1+9=16, aber nicht das Quadrat (34,28), weil 3+4+2+8= 17>16 ,
F: Wie viele Gitter kann dieser Roboter erreichen?
Analyse:
Diese Frage ist relativ einfach und lässt sich in 4 Teile unterteilen:
1) Wie berechnet man die Summe der Ziffern? einer Zahl
2) Ob der Roboter ein bestimmtes Gitter betreten kann
3) Wenn er das Gitter betreten kann, ob die Gitter in den vier benachbarten Bereichen betreten können, # 🎜🎜#
4) Statistiken können insgesamt mehrere Raster erreichen 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><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><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>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;}Das obige ist der detaillierte Inhalt vonSo lösen Sie das Problem, dass Roboter in Java auf dem Gitter laufen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
