-1
  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.

Dan
  • 3,647
  • 5
  • 20
  • 26
TYTA
  • 3
  • 1
  • [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). You're expected to debug the problem, and report back what you see in terms of where your code goes wrong. We don't expect you to fix it, but at the very least, you should give us (and yourself) an idea of where the code goes awry. – PaulMcKenzie May 28 '22 at 13:54

1 Answers1

0

"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. )

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • I tried this solution, but there're some flaws in this solution. Only the starting point was given and the destination is not. So after assigning the new values (absolute value of original weight minus the biggest one), it's always the nearest node (next to the starting node) that creates the cheapest path - which is clearly not the most expensive path in the the original matrix. – TYTA May 31 '22 at 19:07
  • You want the heaviest path to any destination? The usual implementation of Dijsktra will give you the paths drom destination to every other node. You can loop through them all and keep track of which is the heaviest. – ravenspoint May 31 '22 at 19:20