Cherry Pickup trong C ++

Giả sử chúng ta có một lưới N x N, ô này chứa đầy quả anh đào. Mỗi ô có một trong các số nguyên có thể có như sau -

0 - Cho biết ô trống, vì vậy chúng tôi có thể chuyển qua
1 - Cho biết ô chứa một quả anh đào mà chúng ta có thể nhặt và chuyển qua
-1 - Cho biết ô đang chứa một cái gai cản đường

Chúng tôi phải thu thập số lượng anh đào tối đa bằng cách sử dụng một số quy tắc sau -

Bắt đầu từ vị trí (0, 0) và kết thúc tại (N-1, N-1) bằng cách di chuyển sang phải hoặc xuống qua các ô đường dẫn hợp lệ
Sau khi đến ô (N-1, N-1), quay lại (0, 0) bằng cách di chuyển sang trái hoặc lên trên qua các ô đường dẫn hợp lệ;
Khi chúng tôi đi qua một ô đường dẫn có một quả anh đào, chúng tôi nhặt nó lên và ô đó trở thành một ô trống (giá trị sẽ là 0);
Nếu không có đường dẫn hợp lệ giữa (0, 0) và (N-1, N-1) thì không thể thu thập được quả anh đào nào.

Vì vậy, nếu đầu vào giống như -

0	1	-1
1	0	-1
1	1	1

Đầu ra sẽ là 5, bắt đầu từ vị trí (0, 0) và đi xuống, xuống dưới, sang phải, sang phải để đạt (2, 2). Ở đây 4 quả anh đào đã được nhặt trong chuyến đi duy nhất này và ma trận trở thành.

0	1	-1
0	0	-1
0	0	0

Sau đó, chúng ta sẽ đi sang trái, lên, lên, sang trái để quay lại (0,0), nhặt thêm một quả anh đào. Tổng số quả anh đào nhặt được sẽ là 5 quả.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một dir mảng có kích thước:2 x 2:={{1, 0}, {0, 1}}
INF:=10 ^ 9
Xác định một mảng dp có kích thước:51 x 51 x 51.
Xác định một hàm giải quyết (), điều này sẽ lấy r1, c1, c2, một mảng 2D> &lưới,
n:=kích thước của lưới, r2:=r1 + c1 - c2, ret:=0
m:=(nếu n khác 0 thì kích thước của lưới [0], ngược lại là 0)
nếu r1 <0 hoặc c1 <0 hoặc r2 <0 hoặc c2 <0 hoặc r1> =n hoặc r2> =n hoặc c1> =m hoặc c2> =m, thì -
- trả về -INF
nếu lưới [r1, c1] giống -1 hoặc lưới [r2, c2] giống -1, thì -
- trả về -INF
nếu r1 giống với r2 và c1 giống với c2 và r1 giống với n - 1 và c1 giống với m - 1, thì -
- lưới trả về [r1, c1]
nếu dp [r1, c1, c2] không bằng -1, thì -
- trả về dp [r1, c1, c2]
ret:=ret + grid [r1, c1]
nếu r1 giống r2 và c1 giống với c2, thì:không làm gì cả
Mặt khác
- ret:=ret + grid [r2, c2]
tạm thời:=-INF
để khởi tạo k:=0, khi k <2, cập nhật (tăng k lên 1), thực hiện -
- temp:=tối đa của tạm thời và giải quyết (r1 + dir [k, 0], c1 + dir [k, 1], c2 + 1, lưới)
- temp:=tối đa của tạm thời và giải quyết (r1 + dir [k, 0], c1 + dir [k, 1], c2, lưới)
return dp [r1, c1, c2] =ret + temp
Từ phương pháp chính, hãy thực hiện như sau -
Điền dp bằng -1
ret:=giải quyết (0, 0, 0, lưới)
trả về tối đa là 0 và trả về

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
   int dp[51][51][51];
   int solve(int r1, int c1, int c2, vector < vector <int> >& grid){
      int n = grid.size();
      int r2 = r1 + c1 - c2;
      int ret = 0;
      int m = n? grid[0].size() : 0;
      if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
      if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
      if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
      if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
      ret += grid[r1][c1];
      if(r1 == r2 && c1 == c2){
         }else ret += grid[r2][c2];
         int temp = -INF;
         for(int k = 0; k < 2; k++){
         temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
         temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
      }
      return dp[r1][c1][c2] = ret + temp;
   }
   int cherryPickup(vector<vector<int>>& grid) {
      memset(dp, -1, sizeof(dp));
      int ret = solve(0, 0, 0, grid);
      return max(0, ret);
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
   cout << (ob.cherryPickup(v));
}

Đầu vào

{{0,1,-1},{1,0,-1},{1,1,1}}