I have just appeared in an interview where this question was asked.

The problem is:

I have a matrix as follows:

3 3
0 1 -1
1 0 -1
1 1 1

The first line contains row numbers (n) and column numbers (m). Then the following is the given matrix, where 1 means gold piece and -1 means obstacle.

Rules:

  • I have to go from (0, 0) to (n-1, m-1) and then from (n-1, m-1) to (0, 0) back.
  • I can move only to right and down while going from (0, 0) to (n-1, m-1) and only left and up while coming back from (n-1, m-1) to (0, 0).
  • During the above travels, if I encounter a 1, then I pick up that gold piece. Similarly, while coming back if I encounter a 1 on the path I pick up that 1.
  • If at (n-1, m-1) value is -1 or no path to (n-1, m-1) exists then overall gold pieces count is 0.

Problem is to find the maximum number of gold pieces that can be accumulated.

My approach:

During the time of the interview, I deduced that the rules infer that if we merge both the rules for (0, 0) to (n-1, m-1) and from (n-1, m-1) to (0, 0) , we will essentially want to reach (0, 0) to (n-1, m-1) with all possible directions: up, right, down, and left. All I have to do is count the maximum number of 1 while using these 4 path directions.

Then I came up with the following recursive code which does not seem efficient but works.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int mat[100][100];
int lookup[100][100];

int getcount(int pgc, int r, int c) {
    if(r == n-1 && c == m-1) {
        if(mat[r][c] == -1) return 0;
        else return mat[r][c] + pgc;
    }

    int cgc = mat[r][c];
    int tmp1 = 0, tmp2 = 0, tmp3 = 0, tmp4 = 0;

    if (((r + 1) < n) &&( mat[r + 1][c] != -1) && (lookup[r+1][c] != -1)) {
        // go down
        lookup[r + 1][c] = -1;
        tmp1 = getcount(cgc + pgc, r + 1, c);
        lookup[r + 1][c] = 0;
    }

    if (c + 1 < m && mat[r][c + 1] != -1 && lookup[r][c+1] != -1) {
        // go right
        lookup[r][c + 1] = -1;
        tmp2 = getcount(cgc + pgc, r, c + 1);
        lookup[r][c + 1] = 0;
    }
    if (r - 1 >= 0 && mat[r - 1][c] != -1 && lookup[r - 1][c] != -1) {
        // go up
        lookup[r - 1][c] = -1;
        tmp3 = getcount(cgc + pgc, r - 1, c);
        lookup[r - 1][c] = 0;
    }
    if (c - 1 >= 0 && mat[r][c - 1] != -1 && lookup[r][c-1] != -1) {
        // go left
        lookup[r][c - 1] = -1;
        tmp4 = getcount(cgc + pgc, r, c - 1);
        lookup[r][c - 1] = 0;
    }

    return max(tmp1, max(tmp2, max(tmp3, tmp4)));
}

int collectMax() {
    int ans = 0;
    if(mat[n-1][m-1] == -1 || mat[0][0] == -1) ans = 0;
    else {
        int r = 0, c = 0;
        int gc = 0;
        // if(mat[0][0] == 1) gc = 1;
        ans = getcount(gc, r, c);
        ans = max(0, ans);
    } 
    return ans;
}

int main() {
    cin>>n>>m;

    for(int i = 0; i<n; i++) {
        for(int j = 0; j<m; j++) {
            cin>>mat[i][j];
        }
    }

    cout<<collectMax()<<endl;

    return 0;
}

How to make it efficient? Is there a scope of using DP to optimise? Thanks.

Some sample test cases for practice:

Input1:

3 3
0 1 -1
1 0 -1
1 1 1

Output1:

5

Input2:

3 3
0 1 1
1 0 1
1 1 1

Output2:

7

Input3:

3 3
0 1 1
1 0 -1
1 1 -1

Output3:

0

1 Answers

2
ruakh On

This has a solution in O(min(m2nmn2)) time and O(min(m2n2)) space using dynamic programming.

The idea is to consider angled "strips" that look like this (in bold):

0 1 -1
1 0 -1
1 1 1

Your character (= "you", but I want to distinguish between what your program will do in finding the best path and what your character will do in taking the best path) will visit each such strip exactly twice: once on the way from (0, 0) to (m−1, n−1), and once on the way back. This is because each legal move moves from one strip to the adjacent strip in the allowed direction.

So, for each strip, starting with the single-element strip at (0, 0) and ending with the single-element strip at (m−1, n−1), your program will consider all possible pairs of elements in that strip — call them (i1j1) and (i2j2) — and find the maximum number of distinct gold coins that can be obtained on the path from (0, 0) to (i1j1) plus the path from (i2j2) back to (0, 0). For each strip, store the results in a matrix so that it can be used in computing the results for the next strip. (After you've finished a strip, you can discard the results from its previous strip.)

Special cases:

  • Make sure to support "degenerate" pairs where both elements are the same, that is, where i1 = i2. For such pairs, if the element contains a gold coin, make sure to count it only once.
  • Make sure to distinguish an impossible partial path (where either (i1j1) or (i2j2) is an obstacle, or can only be reached via an obstacle) from a partial path that simply doesn't contain any coins. Otherwise you'll mis-process cases like this:

    0  0 -1
    0 -1  1
    0  0  0
    

    where the correct answer is 0 because the lone gold coin is not actually reachable.