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. 来自用户1509803的建议
  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. 切换两个边界比较。 row应该比较map.length，而col应该比较map[0].length。这是因为行可以被认为是垂直堆栈（因此代表二维数组中的第一个索引），而列可以被认为是构成堆栈的水平单元（因此出现在第二个索引中）。考虑先选择堆栈，然后选择堆栈中的单元。

于 2013-09-09T04:20:57.830 回答
1

那么我认为 col 必须小于 (map.length-1) 而不是 (map.length-2) 对于 {1},{1}, map.length == 2 所以 map.length-2 = 0, 然后 col必须小于 0 才能执行 if 块。顺便说一句，你有 map.length 与 col 和 row 的比较，所以你的 map 在任何情况下都是一个正方形？

于 2013-09-09T04:10:30.203 回答