leecode 1463) Cherry Pickup II

LV. Hard 🥵

https://leetcode.com/problems/cherry-pickup-ii/

Cherry Pickup II - LeetCode

 

문제

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

• Robot #1 is located at the top-left corner (0, 0), and
• Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

• From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
• When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
• When both robots stay in the same cell, only one takes the cherries.
• Both robots cannot move outside of the grid at any moment.
• Both robots should reach the bottom row in grid.

 

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

 

Constraints:

• rows == grid.length
• cols == grid[i].length
• 2 <= rows, cols <= 70
• 0 <= grid[i][j] <= 100

 

문제 해결법

처음에 부르트포스로 문제를 풀었다가 타임 아웃이 떠서 다시 dp로 풀게 됨..

 

dp 해결법!

a(0, 0) b(0, cols - 1) 첫 시작점부터 시작해서 순차적으로 계산을 해주었다

a(0, 0) -> a(0 + 1, 0 - 1), a(0 + 1, 0), a(0 + 1, 0 + 1)
b(0, cols - 1) -> b(0 + 1, cols - 2), b(0 + 1, cols - 1), b(0 + 1, cols)

처음에 a와 b는 위와 같이 3곳에 갈 수 있다

계속 밑의 줄로 내려가 밑에서부터 맥스 값을 찾아 위로 올라오면서 더해주는 방식!

가지가 뻗어나가는 모습이라고 말하면 좋으려나..?!

밑에 조건에 따라 필요 없는 가지를 잘라주면서, 추가적인 가지를 만든다

다음과 같은 조건이 나오면 return 해준다

1. y >= rows || x >= cols || x < 0 은 grid 밖의 값이기에 0으로 리턴해준다

2. dp[y][x1][x2]에 값이 저장되어있으면, 이미 a(y, x1) b(y, x2)의 max값을 찾은 것이므로 dp[y][x1][x2] 값을 리턴해준다

 

앞의 상황들을 반복하면서 재귀를 해결하게 되면 정답을 도출 가능!

 

해결 코드

// bruteforce로 풀었을때 time exceed 뜸...

class Robot {
public:
	int x;
	int y;
	Robot (int _x, int _y):x(_x), y(_y) {
	}
};

class Solution {
private:
	int rows;
	int cols;
	int ans;
	vector< vector<int> > grid;

public:
	int cherryPickup(vector< vector<int> >& _grid) {
		vector<vector <bool> > check;

		rows = _grid.size();
		cols = _grid[0].size();
		ans = 0;
		grid = _grid;
		check.assign(rows, vector<bool>(cols, false));
		Robot a(0, 0);
		Robot b(cols - 1, 0);
		cout << ",,,,,,,,,,,,,,,,,,,," << grid[a.y][a.x] + grid[b.y][b.x] << endl;
		findMax(a, b, grid[a.y][a.x] + grid[b.y][b.x], check);
		return ans;
	}
	void findMax(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		moveA1(a, b, maxR, check);
		moveA2(a, b, maxR, check);
		moveA3(a, b, maxR, check);
		moveB1(a, b, maxR, check);
		moveB2(a, b, maxR, check);
		moveB3(a, b, maxR, check);
	}
	void check_max(Robot a, Robot b, int maxR) {
		if (a.y == rows - 1 && b.y == rows - 1) {
			ans = max(maxR, ans);
		}
	}
	// (i + 1, j - 1)
	void moveA1(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi1" << endl;
		if (a.y + 1 < rows && a.x - 1 >= 0 && check[a.y + 1][a.x - 1] == false) {
			a.y += 1;
			a.x -= 1;
			check[a.y][a.x] = true;
			check_max(a, b, maxR + grid[a.y][a.x]);
			findMax(a, b, maxR + grid[a.y][a.x], check);
		}
	}
	// (i + 1, j)
	void moveA2(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi2" << endl;
		if (a.y + 1 < rows && check[a.y + 1][a.x] == false) {
			a.y += 1;
			check[a.y][a.x] = true;
			check_max(a, b, maxR + grid[a.y][a.x]);
			findMax(a, b, maxR + grid[a.y][a.x], check);
		}
	}
	// (i + 1, j + 1)
	void moveA3(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi3" << endl;
		if (a.y + 1 < rows && a.x + 1 < cols && check[a.y + 1][a.x + 1] == false) {
			a.y += 1;
			a.x += 1;
			check[a.y][a.x] = true;
			check_max(a, b, maxR + grid[a.y][a.x]);
			findMax(a, b, maxR + grid[a.y][a.x], check);
		}
	}
	// (i + 1, j - 1)
	void moveB1(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi4 : " << b.y << ", " << b.x << endl;
		if (b.y + 1 < rows && b.x - 1 >= 0 && check[b.y + 1][b.x - 1] == false) {
			b.y += 1;
			b.x -= 1;
			check[b.y][b.x] = true;
			check_max(a, b, maxR + grid[b.y][b.x]);
			findMax(a, b, maxR + grid[b.y][b.x], check);
		}
	}
	// (i + 1, j)
	void moveB2(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi5 : " << b.y << ", " << b.x << endl;
		if (b.y + 1 < rows && check[b.y + 1][b.x] == false) {
			b.y += 1;
			check[b.y][b.x] = true;
			check_max(a, b, maxR + grid[b.y][b.x]);
			findMax(a, b, maxR + grid[b.y][b.x], check);
		}
	}
	// (i + 1, j + 1)
	void moveB3(Robot a, Robot b, int maxR, vector<vector <bool> > check) {
		// cout << "hi6 : " << b.y << ", " << b.x << endl;
		if (b.y + 1 < rows && b.x + 1 < cols && check[b.y + 1][b.x + 1] == false) {
			b.y += 1;
			b.x += 1;
			check[b.y][b.x] = true;
			check_max(a, b, maxR + grid[b.y][b.x]);
			findMax(a, b, maxR + grid[b.y][b.x], check);
		}
	}
};

 

 

//dp로 해결!

class Solution {
private:
	int rows;
	int cols;
	vector< vector < vector<int> > > dp;

public:
	int cherryPickup(vector< vector<int> >& _grid) {

		rows = _grid.size();
		cols = _grid[0].size();
		//dp[y][x1][x2]
		dp.resize(rows, vector< vector<int> >(cols, vector<int>(cols , -1)));
		return findMax(0, 0, cols - 1, _grid);
	}
	int findMax(int y, int x1, int x2, const vector< vector<int> >& _grid) {
		if (y >= rows || x1 >= cols || x2 >= cols || x1 < 0 || x2 < 0)
			return 0;
		if (dp[y][x1][x2] != -1)
			return dp[y][x1][x2];
		int maxVal = _grid[y][x1] + (x1 != x2) * _grid[y][x2];
		for (int i = -1; i <= 1; ++i) {
			for (int j = -1; j <= 1; ++j) {
				dp[y][x1][x2] = max(maxVal + findMax(y + 1, x1 + i, x2 + j, _grid), dp[y][x1][x2]);
			}
		}
		return dp[y][x1][x2];
	}
};