0

だから私は今日の大部分のためにこの問題に取り組んできました。誰かが私がどこで間違ったのかを理解するのを手伝ってくれますか?

コインの数が最も多い場所に移動するため、貪欲です。隣接する場所がコインの宝物を増やしていない場合、移動を停止するため、怠惰です。隣接するいくつかの場所でコインの数が同じである場合、収集者は時計回りに最も高い場所に移動することを選択します。ギャザラーは、訪れた場所からコインを空にします。

 public static int receiveCoins(int[][]map,int r,int c){

        int[] coins = {0,0,0,0}; 

        boolean moreCoins = true;
      int numOfCoins = 0;

        if(map[r][c] > 0){

                  numOfCoins += map[r][c];
                  map[r][c] = 0;                
        }  

        while(moreCoins == true){        

            if(c < (map.length-1)){

                if(map[r][c+1] > 0){

                    coins[1] = map[r][c+1];                
                }               
            }

            if(r < map[0].length-1){

                if(map[r+1][c] > 0){

                    coins[2] = map[r+1][c];

                }               
            }

               if(row > 0){
                if(map[r-1][c] > 0){

                    coins[0] = map[r-1][c];

                }
            }


            if(c > 0){

                if(map[r][c-1] > 0){

                    coins[3] = map[r][c-1];

                }               
            }           

            int maxCoin = 0;
            int nRow = 0;
            int nCol = 0;

            for(int i = 0; i < coins.length; i++){

                if(coins[i] > maxCoin){

                    maxCoin = coins[i];

                    if(i == 0){
                        nCol = c;
                        nRow = r - 1;

                    }else if(i == 1){
                        nRow = r;
                        nCol = c + 1;

                    }else if(i == 2){
                        nCol = c;
                        nRow = r + 1;

                    }else{
                        nRow = r;
                        nCol = c - 1;

                    }

                }   
                coins[i] = 0; 
            }           
                }               
            }

            if (maxCoin == 0){

                moreCoins = false;

            }else{                          

                r = nRow;
                c = nCol; 

                numOfCoins += map[r][c];
                map[r][c] = 0;


            }   
        }

        return numOfCoins;   
    }
4

2 に答える 2

2

アルゴリズムのいくつかの修正:

  1. user1509803からの提案
  2. coins[]次の反復で前の反復の値を再利用しないように、最高値を確認した後、ゼロにリセットする必要があります。たとえば、ある反復で値が非ゼロで、次の反復でゼロである場合。

  3. break終盤に近いのはなぜ？これにより、ループの最初の繰り返しの後でプログラムが常に中断されます。while

      map[row][col] = 0;

  if(map[row][col] == 0){
      break; // why?
  }

  4. 最高値の次の位置を確認するときは、前の位置が最高であると識別された場合に備えて、行と列の両方を設定してください。

        if(coins[i] > highestCoin){

        highestCoin = coins[i];

        if(i == 0){
            newCol = col; // this is important! do this for all cases!
            newRow = row - 1;

        }   
        ...     
    }

  5. 2 つの境界比較を切り替えます。 rowと比較する必要がmap.lengthありますが、colと比較する必要がありmap[0].lengthます。これは、行が垂直方向のスタック (したがって 2 次元配列の最初のインデックスを表す) と見なすことができるのに対し、列はスタックを構成する水平方向の単位 (したがって 2 番目のインデックスに表示される) と見なすことができるためです。最初にスタックを選択し、次にスタック内のユニットを選択することを考えてください。

于 2013-09-09T04:20:57.830 に答える