java - 遍历矩阵的匝数时的最大和

Question

你有一个矩阵，你可以从任何一点开始。您可以朝 8 个方向中的任意一个方向移动(下、左下、左、左上等)。对于您所在的每个位置，您都将该位置的值添加到总和中。当你到达一个位置后，它的值就变成0。挑战包括创建一个递归算法，用于返回从给定点开始的最高总和。

我的问题是:我的方法不起作用。你能帮我修改我的方法使其起作用吗？

这是我的代码:

public int travel (int i, int j,int k,int sum)
    {
        //value temporarily takes the position's value
        int value;

        //if position is out of matrix bounds
        if(i>=x||j>=y||i<0||j<0)
        {
            return 0;
        }
        else
        {
            //makes the value in point (i,j) = 0
            value=M[i][j];
            M[i][j]=0;

            //if the number of turns has been reached
            if(k==turns)
            {
                //restores value at position
                M[i][j]=value;
                return M[i][j];
            }
            else
            {
                //loop for going to all 8 neighbors
                for(int line=-1;line<2;line++)
                {
                    for(int col=-1;col<2;col++)
                    {
                        //if the position is the same
                        if(!(col==0&&line==0))
                        {
                            sum=Math.max(travel(i+line,j+col,k+1,sum), sum);
                        }
                    }
                }

                //restores value at position
                M[i][j]=value;

                //returns sum so far
                return sum+M[i][j];
            }
        }
    }

对于矩阵:

    9 2 7 4 
    2 8 3 7
    5 1 2 4
    1 9 8 3

turns: 3
starting point: (0,0) (of value 9)

它应该返回31。路径是右下，右上，右下(9+8+7+7=31)

Answer 1

工作代码:

   public static int travel (int i, int j,int k)
   {
    //value temporarily takes the position's value
    int value;

    //if position is out of matrix bounds
    if(i>=x||j>=y||i<0||j<0)
    {
        return 0;
    }
    else
    {
        //makes the value in point (i,j) = 0
        value=M[i][j];
        M[i][j]=0;

        //if the number of turns has been reached
        if(k==turns)
        {
            //restores value at position
            M[i][j]=value;
            return M[i][j];
        }
        else
        {   
            int sum = 0;
            //loop for going to all 8 neighbors
            for(int line=-1;line<2;line++)
            {
                for(int col=-1;col<2;col++)
                {
                    //if the position is the same
                    if(!(col==0&&line==0))
                    {
                        sum=Math.max(travel(i+line,j+col,k+1), sum);
                    }
                }
            }

            //restores value at position
            M[i][j]=value;

            //returns sum so far
            return sum+M[i][j];
        }
    }
}

您的代码的问题在于 sum 参数。因为，经过一个回合，sum值已经更新了，你也将这个更新后的值传递给下一个回合，这就使得整个事情变得越来越大