找出你可以挑选的最大苹果，确保你在T时间之前到达右下角细胞

Question

从给定网格的左上角单元格开始。有些细胞有墙，有些细胞你可以走路，有些细胞有苹果。给你一个时间限制= T，你应该在最多的T时间到达右下角的单元格。找出你能收集到的苹果的最大数量。你不能两次访问一个牢房。N，M，T <= 14。

我尝试了很多的想法，最有希望的一个是这个-转换问题，因为找到最短的时间到目的地收集至少X个苹果。然后我们可以对苹果的数量进行二进制搜索。但我无法确定最后6个小时的解决方案。“你不能访问一个牢房两次。”这给我带来了麻烦。

任何其他的想法或暗示都会受到赞赏。

Answer 1

你试过回溯了吗？像这样吗？

​

// 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));

​

Answer 2

给定这些约束，您可以使用一个简单的递归函数来完成问题。

设solve(i,j,steps,vis)是函数，其中(i,j)是当前坐标，time是剩余时间，vis是当前访问的节点集。答案将是solve(0,0,T,[])。

简单的递归是(使用伪代码)：

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