1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std;
class Solution { public: int orangesRotting(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); memset(badTime, -1, sizeof(badTime)); queue<pair<int, int>> badOranges; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) { badOranges.emplace(i, j); badTime[i][j] = 0; } else if (grid[i][j] == 1) { count++; } } }
int res = 0; while (!badOranges.empty()) { auto badOrange = badOranges.front(); badOranges.pop(); int row = badOrange.first, col = badOrange.second;
for (int i = 0; i < 4; i++) { int x = row + dx[i], y = col + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && badTime[x][y] == -1 && grid[x][y] != 0) { badTime[x][y] = badTime[row][col] + 1; badOranges.emplace(x, y);
if (grid[x][y] == 1) { grid[x][y] = 2; count--; res = badTime[x][y]; if (count == 0) { break; } } } } }
return count == 0 ? res : -1; }
private: static const int N = 10; int badTime[N][N]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; };
void printArray(const vector<vector<int>>& nums) { cout << "["; for (size_t i = 0; i < nums.size(); i++) { cout << "["; for (size_t j = 0; j < nums[i].size(); j++) { cout << nums[i][j]; if (j != nums[i].size() - 1) cout << ","; } cout << "]"; if (i != nums.size() - 1) cout << ","; } cout << "]" << endl; }
int main() { Solution solution; vector<vector<vector<int>>> grid_cases = { {{2,1,1},{1,1,0},{0,1,1}}, {{2,1,1},{0,1,1},{1,0,1}}, {{0,2}} };
for (int i = 0; i < grid_cases.size(); i++) { auto& grid = grid_cases[i]; cout << "Input: grid = "; printArray(grid);
int result = solution.orangesRotting(grid); cout << "Output: " << result << endl; }
return 0; }
|