1. There's a matrix, each of its cell contains an integer value (both positive and negative). You're given an initial position in the matrix, now you have to find a path that the sum of all the cells you've crossed is the biggest. You can go up, down, right, left and only cross a cell once.
2. My solution is using Bellman Ford algorithm: Let's replace all the values by their opposite number, now we've just got a new matrix. Then, I create an undirected graph from the new matrix, each cell is a node, stepping on a cell costs that cell's value - it's the weight. So, I just need to find the shortest path of the graph using Bellman-Ford algorithm. That path will be the longest path of our initial matrix. Well, there's a problem. The graph contains negative cycles, also has too many nodes and edges. The result, therefore, isn't correct.
3. This is my code:

Knowing that xd and yd is the initial coordinate of the robot.

void MatrixToEdgelist()
{
    int k = 0;
    for (int i=1;i<=n;i  )
        for (int j=1;j<=n;j  )
    {
        int x = (i - 1) * n   j;
        int y = x   1;
        int z = x   n;
        if (j<n)
        {
            edges.push_back(make_tuple(x, y, a[i][j 1]));
        }
        if (i<n)
        {
            edges.push_back(make_tuple(x, z, a[i 1][j]));
        }
    }
}

   void BellmanFord(Robot r){
        int x = r.getXd();
        int y = r.getYd();
        int z = (x-1)*n   y;
        int l = n*n;
        int distance[100];
        int previous[100]{};
        int trace[100];
    
        trace[1] = z;
        for (int i = 1; i <= l; i  ) {
            distance[i] = INF;
        }
    
        distance[z] = a[x][y];
        for (int i = 1; i <= l-1; i  ) {
            for (auto e : edges) {
                int a, b, w;
                tie(a, b, w) = e;
                //distance[b] = min(distance[b], distance[a] w);
                if (distance[b] < distance[a]   w)// && previous[a] != b)
                {
                    distance[b] = distance[a]   w;
                    previous[b] = a;
                }
            }
    
        }
    
        //print result
        int Max=INF;
        int node;
        for (int i=2;i<=l;i  )
        {
            if (Max < distance[i])
            {
                Max = distance[i];
                node = i;
            }
        }
    
        if (Max<0)cout << Max << "\n";
        else cout << Max << "\n";
        vector<int> ans;
        int i = node;
        ans.push_back(i);
        while (i != z)
        {
            i = previous[i];
            ans.push_back(i);
        }
    
        for (int i=ans.size()-1;i>=0;i--)
        {
            int x, y;
            if (ans[i] % n == 0)
            {
                x = ans[i] / n;
                y = n;
            }
            else{
                x = ans[i] / n   1;
                y = ans[i] - (( x - 1 ) * n);
            }
            cout << x << " " << y << "\n";
        }
    }

Example matrix

The result

Clearly that the distance should have continued to update, but it doesn't. It stops at the final node.

CodePudding user response：

"Let's replace all the values by their opposite number"

Not sure what you mean by an opposite number. Anyway, that is incorrect.

If you have negative weights, then the usual solution is to add the absolute value of the most negative weight to EVERY weight.

Why Bellman-Ford? Dijkstra should be sufficient for this problem. ( By default Dijkstra finds the cheapest path. You find the most expensive by assigning the absolute value of ( the original weight minus the greatest ) to every link. )