0994 added.

liuyubobobo · liuyubobobo · commit add55146eea8 · 2019-02-18T17:39:05.000-08:00
diff --git a/0994-Rotting-Oranges/cpp-0994/CMakeLists.txt b/0994-Rotting-Oranges/cpp-0994/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(B)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(B main2.cpp)
diff --git a/0994-Rotting-Oranges/cpp-0994/main.cpp b/0994-Rotting-Oranges/cpp-0994/main.cpp
@@ -0,0 +1,106 @@
+/// Source : https://leetcode.com/problems/rotting-oranges/
+/// Author : liuyubobobo
+/// Time   : 2019-02-16
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Simulation
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
+    int m, n;
+
+public:
+    int orangesRotting(vector<vector<int>>& grid) {
+
+        assert(grid.size() && grid[0].size());
+        m = grid.size(), n = grid[0].size();
+
+        vector<int> rotten;
+        int fresh = 0;
+        for(int i = 0; i < m; i ++)
+            for(int j = 0; j < n; j ++)
+                if(grid[i][j] == 1)
+                    fresh ++;
+                else if(grid[i][j] == 2)
+                    rotten.push_back(i * n + j);
+
+        if(!rotten.size())
+            return fresh ? -1 : 0;
+
+        unordered_set<int> used;
+        for(int e: rotten) used.insert(e);
+
+        int res = 0;
+        while(rotten.size()){
+
+//            cout << "rotten : ";
+//            for(int e: rotten) cout << e << " ";
+//            cout << endl;
+
+            vector<int> newrotten;
+            for(int e: rotten){
+                int x = e / n, y = e % n;
+                for(int i = 0; i < 4; i ++){
+                    int nextx = x + d[i][0], nexty = y + d[i][1];
+                    if(nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && grid[nextx][nexty] == 1){
+                        grid[nextx][nexty] = 2;
+                        newrotten.push_back(nextx * n + nexty);
+                        used.insert(nextx * n + nexty);
+                    }
+                }
+            }
+
+            if(newrotten.size()) res ++;
+            rotten = newrotten;
+        }
+
+        if(!allRotten(grid)) return -1;
+        return res;
+    }
+
+private:
+    bool allRotten(const vector<vector<int>>& grid){
+        for(int i = 0; i < m; i ++)
+            for(int j = 0; j < n; j ++)
+                if(grid[i][j] == 1)
+                    return false;
+        return true;
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> grid1 = {
+            {2,1,1},
+            {1,1,0},
+            {0,1,1}
+    };
+    cout << Solution().orangesRotting(grid1) << endl;
+    // 4
+
+    vector<vector<int>> grid2 = {
+            {0, 0},
+            {0, 0}
+    };
+    cout << Solution().orangesRotting(grid2) << endl;
+    // 0
+
+    vector<vector<int>> grid3 = {
+            {1}
+    };
+    cout << Solution().orangesRotting(grid3) << endl;
+    // -1
+
+    return 0;
+}
diff --git a/0994-Rotting-Oranges/cpp-0994/main2.cpp b/0994-Rotting-Oranges/cpp-0994/main2.cpp
@@ -0,0 +1,99 @@
+/// Source : https://leetcode.com/problems/rotting-oranges/
+/// Author : liuyubobobo
+/// Time   : 2019-02-16
+
+#include <iostream>
+#include <queue>
+#include <cassert>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// BFS
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
+    int m, n;
+
+public:
+    int orangesRotting(vector<vector<int>>& grid) {
+
+        assert(grid.size() && grid[0].size());
+        m = grid.size(), n = grid[0].size();
+
+        queue<pair<int, int>> q;
+        unordered_set<int> used;
+        int fresh = 0;
+        for(int i = 0; i < m; i ++)
+            for(int j = 0; j < n; j ++)
+                if(grid[i][j] == 2){
+                    int pos = i * n + j;
+                    q.push(make_pair(pos, 0));
+                    used.insert(pos);
+                }
+
+        int res = 0;
+        while(!q.empty()){
+
+            int cur = q.front().first;
+            int step = q.front().second;
+            q.pop();
+
+            res = max(res, step);
+
+            int x = cur / n, y = cur % n;
+            for(int i = 0; i < 4; i ++){
+                int nextx = x + d[i][0], nexty = y + d[i][1];
+                if(nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && grid[nextx][nexty] == 1){
+                    int nextpos = nextx * n + nexty;
+                    grid[nextx][nexty] = 2;
+                    q.push(make_pair(nextpos, step + 1));
+                    used.insert(nextpos);
+                }
+            }
+        }
+
+        if(!allRotten(grid)) return -1;
+        return res;
+    }
+
+private:
+    bool allRotten(const vector<vector<int>>& grid){
+        for(int i = 0; i < m; i ++)
+            for(int j = 0; j < n; j ++)
+                if(grid[i][j] == 1)
+                    return false;
+        return true;
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> grid1 = {
+            {2,1,1},
+            {1,1,0},
+            {0,1,1}
+    };
+    cout << Solution().orangesRotting(grid1) << endl;
+    // 4
+
+    vector<vector<int>> grid2 = {
+            {0, 0},
+            {0, 0}
+    };
+    cout << Solution().orangesRotting(grid2) << endl;
+    // 0
+
+    vector<vector<int>> grid3 = {
+            {1}
+    };
+    cout << Solution().orangesRotting(grid3) << endl;
+    // -1
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -658,4 +658,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 991 | [Broken Calculator](https://leetcode.com/problems/broken-calculator/) | [solution](https://leetcode.com/problems/broken-calculator/solution/) | [C++](0991-Broken-Calculator/cpp-0991/) | | |
 | 992 | [Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/) | [solution](https://leetcode.com/problems/subarrays-with-k-different-integers/solution/) | [C++](0992-Subarrays-with-K-Different-Integers/cpp-0992/) | | |
 | 993 | [Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/) | [solution](https://leetcode.com/problems/cousins-in-binary-tree/solution/) | [C++](0993-Cousins-in-Binary-Tree/cpp-0993/) | | |
+| 994 | [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) | [solution](https://leetcode.com/problems/rotting-oranges/solution/) | [C++](0994-Rotting-Oranges/cpp-0994/) | | |
 | | | | | | |
