LeetCode #994 RottingOranges. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
Performance was Comme ci comme ca
Runtime: 8 ms, faster than 71.18% of C++ online submissions for Rotting Oranges.
Memory Usage: 9.1 MB, less than 71.94% of C++ online submissions for Rotting Oranges.
LeetCode #994
Q.
In a given grid, each cell can have one of three values:
- the value 0 representing an empty cell;
- the value 1 representing a fresh orange;
- the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
주어진 그리드에서, 각 셀은 아래 세개중 하나의 값을 갖는다:
- 0 은 빈 칸을 의미한다.
- 1 은 프레시한 오렌지를 의미한다.
- 2 는 상한 오렌지를 의미한다.
매 분마다, 상한 오렌지의 4방향으로 붙어있는 프레시 오렌지는 상한 오렌지로 바뀐다.
모든 셀에 프레시한 오렌지가 남지 않게되는 최소의 시간(분)을 반환해라. 만약 전부 상하는게 불가능하다면 -1 을 리턴해라.
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- grid[i][j] is only 0, 1, or 2.
Process
// Process
//1. Input grid
//2. Count all fresh (freshCount)
//3. Make rottenVector (coord of rottenOrange)
//4. Iterate while rottenVector size > 0
// 4.1. Iterate rottenVector from begin to the end (i)
// 4.1.1. Check up/down/left/right coord if it's fresh, if so - check rotten and put coord to rottenVector
// 4.1.2. Remove that rottenVector[i]
// 4.1.3. Count minutes
// 4.1.4. Minus freshCount
//5. Check if freshCount is 0, if not -> return -1
//6. Finish
// 처리과정
//1. 그리드 입력받는다.
//2. 전체에서 fresh 개수 세어놓는다.
//3. 최초 rottenVector (최초 rottenOrange 좌표) 만들어둔다.
//4. rottenVector size > 0 이면 반복한다.
// 4.1. rottenVector 전체 반복한다.
// 4.1.1. 상하좌우 중, 그리드 내에 있고 fresh 한 부분을 rottenVector 에 넣고 그리드에 상했다고 표시한다.
// 4.1.2. 기존 rotten 값은 vector 에서 지운다
// 4.1.3. minutes 센다
// 4.1.4. fresh 개수 뺀다.
//5. fresh 개수 0 이 아니면 -1 을 반환한다.
//6. 끝낸다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int minutes = 0;
bool isInvalid = false;
vector<pair<int, int>> rottenVector;
int freshCount = 0;
// 2. / 3.
CheckingGrid(grid, &rottenVector, &freshCount);
cout << freshCount << endl;
// 4.
int m = 0;
int n = 0;
vector<pair<int, int>> tempRottenVector;
bool madeRot;
while (rottenVector.size() > 0) {
madeRot = false;
tempRottenVector.clear();
for (int i = 0; i < rottenVector.size(); ++i) {
m = rottenVector.at(i).first;
n = rottenVector.at(i).second;
if (m - 1 >= 0 && grid[m - 1][n] == 1) {
grid[m - 1][n] = 2;
tempRottenVector.push_back(make_pair(m - 1, n));
madeRot = true;
--freshCount;
}
if (n + 1 < grid[0].size() && grid[m][n + 1] == 1) {
grid[m][n + 1] = 2;
tempRottenVector.push_back(make_pair(m, n + 1));
madeRot = true;
--freshCount;
}
if (m + 1 < grid.size() && grid[m + 1][n] == 1) {
grid[m + 1][n] = 2;
tempRottenVector.push_back(make_pair(m + 1, n));
madeRot = true;
--freshCount;
}
if (n - 1 >= 0 && grid[m][n - 1] == 1) {
grid[m][n - 1] = 2;
tempRottenVector.push_back(make_pair(m, n - 1));
madeRot = true;
--freshCount;
}
}
if (madeRot) {
++minutes;
}
rottenVector = tempRottenVector;
}
if (freshCount != 0)
return -1;
// 5.
return minutes;
}
private:
bool CheckingGrid(vector<vector<int>>& grid, vector<pair<int, int>>* rottenVector, int* freshCount) {
bool isInvalid = false;
for (int i = 0; !isInvalid && i < grid.size(); ++i) {
for (int j = 0; !isInvalid && j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
++*freshCount;
}
else if (grid[i][j] == 2) {
rottenVector->push_back(make_pair(i, j));
}
}
}
return isInvalid;
}
};
Something else you might like...?
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법
