하나의 N x N 그리드가 있다고 가정하고 이것은 체리로 채워져 있습니다. 각 셀에는 다음과 같이 가능한 정수 중 하나가 있습니다. -
- 0 - 셀이 비어 있으므로 통과할 수 있음을 나타냅니다.
- 1 - 셀에 체리가 포함되어 있음을 나타냅니다. 체리를 집어서 통과할 수 있습니다.
- -1 - 세포가 길을 막는 가시를 포함하고 있음을 나타냅니다.
우리는 이 몇 가지 규칙을 사용하여 최대 수의 체리를 수집해야 합니다 -
- 유효한 경로 셀을 통해 오른쪽 또는 아래로 이동하여 위치(0, 0)에서 시작하여 (N-1, N-1)에서 끝납니다.
- 셀(N-1, N-1)에 도달한 후 유효한 경로 셀을 통해 왼쪽 또는 위로 이동하여 (0, 0)으로 돌아갑니다.
- 체리가 포함된 경로 셀을 통과할 때 체리를 선택하면 셀이 빈 셀이 됩니다(값은 0).
- (0, 0)과 (N-1, N-1) 사이에 유효한 경로가 없으면 체리를 수집할 수 없습니다.
따라서 입력이 다음과 같으면 -
| 0 | 1 | -1 |
| 1 | 0 | -1 |
| 1 | 1 | 1 |
출력은 위치 (0, 0)에서 시작하여 아래로, 아래로, 오른쪽으로, (2, 2)에 도달할 때까지 5가 됩니다. 이번 한 번의 여행에서 4개의 체리가 주워져 매트릭스가 됩니다.
| 0 | 1 | -1 |
| 0 | 0 | -1 |
| 0 | 0 | 0 |
그런 다음 왼쪽, 위쪽, 위쪽, 왼쪽으로 이동하여 (0,0)으로 돌아가 체리를 하나 더 줍습니다. 줍는 체리의 총 개수는 5개입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 배열 디렉토리 크기 정의:2 x 2 :={{1, 0}, {0, 1}}
- INF :=10^9
- 51 x 51 x 51 크기의 배열 dp를 정의합니다.
- solve() 함수를 정의하면 r1, c1, c2, 하나의 2D 배열>&그리드,
- n :=그리드 크기, r2 :=r1 + c1 - c2, ret :=0
- m :=(n이 0이 아니면 grid[0]의 크기, 그렇지 않으면 0)
- r1 <0 또는 c1 <0 또는 r2 <0 또는 c2 <0 또는 r1>=n 또는 r2>=n 또는 c1>=m 또는 c2>=m이면 −
- 반환 -INF
- grid[r1, c1]이 -1과 같거나 grid[r2, c2]가 -1과 같으면 -
- 반환 -INF
- r1이 r2와 같고 c1이 c2와 같고 r1이 n - 1과 같고 c1이 m - 1과 같으면 -
- 리턴 그리드[r1, c1]
- dp[r1, c1, c2]가 -1과 같지 않으면 -
- dp[r1, c1, c2]를 반환
- ret :=ret + 그리드[r1, c1]
- r1이 r2와 같고 c1이 c2와 같으면 아무 것도 하지 않음
- 그렇지 않으면
- ret :=ret + 그리드[r2, c2]
- temp :=-INF
- 초기화 k의 경우:=0, k <2일 때 업데이트(k를 1만큼 증가), 수행 -
- temp :=temp 및 solve(r1 + dir[k, 0], c1 + dir[k, 1], c2 + 1, grid)의 최대값
- temp :=temp 및 solve(r1 + dir[k, 0], c1 + dir[k, 1], c2, grid)의 최대값
- 반환 dp[r1, c1, c2] =ret + temp
- 메인 방법에서 다음을 수행하십시오. -
- dp를 -1로 채우기
- ret :=해결(0, 0, 0, 그리드)
- 최대값을 0으로 반환하고 ret
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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));
} 입력
{{0,1,-1},{1,0,-1},{1,1,1}} 출력
5