Coding Test/LeetCode
[LeetCode] 994. Rotting Oranges c++
owls
2023. 1. 4. 19:10
728x90
문제
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent 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.
2는 썩은 오렌지, 1은 신선한 오렌지를 의미합니다.
매 분마다 썩은 오렌지(2)가 있는 위치에서 상하좌우에 신선한 오렌지가 있다면 썩은 오렌지로 감염시킵니다.
신선한 오렌지가 없어지는 최소 시간을 찾는 문제입니다.
문제 해결
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<int> dir{ -1, 0, 1, 0, -1 };
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
q.push({ i, j });
}
if (grid[i][j] == 1) {
fresh++;
}
}
}
int ans = -1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
pair<int, int> p = q.front(); //auto& [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int r = p.first + dir[i];
int c = p.second + dir[i + 1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
grid[r][c] = 2;
q.push({ r, c });
fresh--;
}
}
}
ans++;
}
return (fresh > 0) ? -1 : (( ans == -1) ? 0 : ans);
/*
if (fresh > 0) {
return -1;
}
if (ans == -1) {
return 0;
}
return ans;
*/
}
};
728x90