Find max apples you can pick ensuring you reach bottom right cell by time T

user_1192497 0
Viewed 294

You start at top-left cell of a given grid. Some cells have wall, some you can walk, and some cells have apple. You are given a time limit = T, and you should reach bottom right cell by atmost T time. Find maximum number of apples you can collect. You cannot visit a cell twice. N, M, T <= 14.

I tried a lot of ideas, most promising one is this - rephrase problem as find shortest time to reach destination collecting atleast X apples. Then we could binary search on number of apples. But I am not able to pin down a solution from last 6hours. "You cannot visit a cell twice." this is causing me problem.

Any other idea or hint is appreciated.

shortest-path dynamic-programming graph algorithm
2 Answers

Have you tried backtracking? Something like this?

// Heuristic: Manhattan distance to end
function dist(y, x, n, m){
  return n - y + m - x - 2;
}

function getNext(i, j, n, m){
  const ways = [];
  if (i + 1 < n)
    ways.push([i+1, j]);
  if (i > 0)
    ways.push([i-1, j]);
  if (j + 1 < m)
    ways.push([i, j+1]);
  if (j > 0)
    ways.push([i, j-1]);
  return ways;
}

function f(M, T){
  const WALL = 2;
  const n = M.length;
  const m = M[0].length;
  const visited = new Array(n);
  for (let i=0; i<n; i++)
    visited[i] = new Array(m).fill(0);
  let best = 0;
  
  function backtrack(i, j, t, k){
    if (i == n-1 && j == m-1){
      best = Math.max(best, k + M[i][j]);
      return;
    }
 
    for (const [ii, jj] of getNext(i, j, n, m)){
      if (!visited[ii][jj] &&
        M[ii][jj] != WALL &&
        t + dist(ii, jj, n, m) <= T){
        visited[ii][jj] = 1;
        backtrack(ii, jj, t + 1, k + M[i][j]);
        visited[ii][jj] = 0
      }
    }
  }
  
  backtrack(0, 0, 0, 0);
  return best;
}

var N = 8;
var M = 8;
var T = 14;

var matrix = new Array(N);
for (let i=0; i<N; i++)
  matrix[i] = new Array(M).fill(0);
// Apples
matrix[5][5] = 1;
matrix[5][6] = 1;
// Walls
matrix[5][7] = 2;
matrix[5][4] = 2;
matrix[4][4] = 2;
matrix[4][5] = 2;
  
console.log(f(matrix, T));

matrix[5][4] = 0;

console.log(f(matrix, T));

user_20347870

Given the constraints, you can use a simple recursive function to complete the problem.

Let solve(i,j,steps,vis) be the function, where (i,j) are current coordinates, time is the time remaining, and vis is the set of currently visited nodes. The answer will be solve(0,0,T,[]).
The simple recursion would be (using pseudo-code):

def solve(i,j,t,vis):
    if (i<0 or i>=n or j<0 or j>=m) return -1
    if ((i,j) in vis) return -1
    if (cell[i][j] == WALL) return -1
    if (t==0){
        if (i==n-1 and j==m-1) return cell[i][j]
        else return -1
    }
    if (i==n-1 and j==m-1) return cell[i][j]

    max_here = cell[i][j]
    temp = max(solve(i,j+1,t-1,vis+(i,j)), solve(i,j-1,t-1,vis+(i,j)), solve(i+1,j,t- 
               1,vis+(i,j)), solve(i-1,j,t-1,vis+(i,j)))  #assuming movement in 4 directions
    if (temp==-1) return -1   # since none of the neighbours lead to destination
    return max_here+temp
user_93507200
Related