C++의 썩어가는 오렌지

<시간/>

그리드가 있다고 가정하고 여기 각 셀에는 세 가지 값 중 하나가 있을 수 있습니다. -

빈 셀의 경우 값 0;
신선한 오렌지의 경우 값 1,
썩은 오렌지의 경우 값 2.

1분마다 썩은 오렌지 옆에 있는 신선한 오렌지는 썩게 됩니다.

세포에 신선한 오렌지가 없을 때까지 경과해야 하는 최소 횟수를 찾아야 합니다. 이것이 불가능하면 -1을 반환합니다.

따라서 입력이 [[2,1,1],[1,1,0],[0,1,1]]과 같으면 출력은 4

가 됩니다.

C++의 썩어가는 오렌지

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

분 :=0
rowMax :=그리드의 행 크기
colMax :=그리드의 열 크기
freshLeft :=거짓
newGrid :=그리드
true가 0이 아닌 동안 수행 -
- newGrid :=그리드
- 플래그 :=거짓
- freshLeft :=거짓
- initialize i :=0의 경우 i
  - j 초기화의 경우:=0, j
    - newGrid[i, j]가 1과 같으면 -
      - if (i-1>=0이고 newGrid[i-1,j]가 2) 또는 (i+1 =0이고 newGrid[ i,j-1]은 2) 또는 (j+1>=0이고 newGrid[i,j+1]은 2)이고
        
        그리드[i, j] :=2
        
        플래그 :=참
      - freshLeft :=참
- 플래그가 0이 아닌 경우 -
  - (분 1씩 증가)
- 그렇지 않으면
  - 루프에서 나오세요
return(freshLeft가 true가 아니면 분, 그렇지 않으면 -1)

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int orangesRotting(vector<vector<int>> &grid) {
      int minutes = 0;
      int rowMax = grid.size();
      int colMax = grid[0].size();
      bool freshLeft = false;
      auto newGrid = grid;
      while (true) {
         newGrid = grid;
         bool flag = false;
         freshLeft = false;
         for (int i = 0; i < rowMax; i++) {
            for (int j = 0; j < colMax; j++) {
               if (newGrid[i][j] == 1) {
                  if ((i - 1 >= 0 && newGrid[i - 1][j] == 2) or (i + 1 < rowMax && newGrid[i + 1][j] == 2) or (j - 1 >= 0 && newGrid[i][j - 1] == 2) or (j + 1 < colMax && newGrid[i][j + 1] == 2)) {
                     grid[i][j] = 2;
                     flag = true;
                  }
                  freshLeft = true;
               }
            }
         }
         if (flag)
            minutes++;
         else
            break;
      }
      return (freshLeft != true) ? minutes : -1;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
   cout << (ob.orangesRotting(v));
}

입력

{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}