Bagaimana untuk menyelesaikan masalah robot berjalan di grid di Jawa

Tajuk: Terdapat grid dengan m baris dan n lajur pada peta Sebuah robot mula bergerak dari grid pada koordinat (0,0) Arah yang ia boleh bergerak setiap kali adalah atas, bawah, kiri dan betul, dan setiap kali Anda hanya boleh mengalihkan satu grid, tetapi anda tidak boleh memasukkan grid yang jumlah koordinat baris dan koordinat lajur lebih besar daripada K. Sebagai contoh, apabila K ialah 16, robot boleh memasukkan segi empat sama (24,19) kerana 2+4+1+9=16, tetapi tidak boleh memasukkan segi empat sama (34,28) kerana 3+4+2+8= 17>16 ,

S: Berapa banyak grid yang boleh dicapai oleh robot ini?

Analisis:

Soalan ini agak mudah dan boleh dipecahkan kepada 4 bahagian:

1) Bagaimana untuk mengira jumlah digit bagi suatu nombor

2) Sama ada robot boleh memasuki grid tertentu

3) Jika ia boleh memasuki grid, sama ada grid dalam empat kejiranan boleh masuk,

4) Statistik boleh mencapai berbilang grid dalam jumlah

1) Kod

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

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

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

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

Atas ialah kandungan terperinci Bagaimana untuk menyelesaikan masalah robot berjalan di grid di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!