3418. Maximum Amount of Money Robot Can Earn

You are given an m x n grid. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). The robot can move either right or down at any point in time.

The grid contains a value coins[i][j] in each cell:

• If coins[i][j] >= 0, the robot gains that many coins.
• If coins[i][j] < 0, the robot encounters a robber, and the robber steals the absolute value of coins[i][j] coins.

The robot has a special ability to neutralize robbers in at most 2 cells on its path, preventing them from stealing coins in those cells.

Note: The robot’s total coins can be negative.

Return the maximum profit the robot can gain on the route.

c++

class Solution {
    long long vis[4][505][505];
public:
    long long maximumAmount(vector<vector<int>>& coins) {
        int n = coins.size(), m = coins[0].size();
        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) vis[0][i][j] = vis[1][i][j] = vis[2][i][j] = INT_MIN;
        vis[0][0][0] = coins[0][0];
        vis[1][0][0] = 0;
        for(int k = 0; k < 3; k++) {
            for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
                if(i + 1 < n) {
                    vis[k][i+1][j] = max(vis[k][i+1][j], vis[k][i][j] + coins[i+1][j]);
                    vis[k+1][i+1][j] = max(vis[k+1][i+1][j], vis[k][i][j]);
                }
                if(j + 1 < m) {
                    vis[k][i][j+1] = max(vis[k][i][j+1], vis[k][i][j] + coins[i][j+1]);
                    vis[k+1][i][j+1] = max(vis[k+1][i][j+1], vis[k][i][j]);
                }
            }
        }
        return max({vis[0][n-1][m-1], vis[1][n-1][m-1], vis[2][n-1][m-1]});
    }
};