{"id":4862,"date":"2019-02-16T23:37:10","date_gmt":"2019-02-17T07:37:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4862"},"modified":"2019-02-16T23:37:47","modified_gmt":"2019-02-17T07:37:47","slug":"leetcode-994-rotting-oranges","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-994-rotting-oranges\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 994. Rotting Oranges"},"content":{"rendered":"\n<p>In a given grid, each cell can have one of three&nbsp;values:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>the value&nbsp;<code>0<\/code>&nbsp;representing an empty cell;<\/li><li>the value&nbsp;<code>1<\/code>&nbsp;representing a fresh orange;<\/li><li>the value&nbsp;<code>2<\/code>&nbsp;representing a rotten orange.<\/li><\/ul>\n\n\n\n<p>Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.<\/p>\n\n\n\n<p>Return the minimum number of minutes that must elapse until no cell has a fresh orange.&nbsp; If this is impossible, return&nbsp;<code>-1<\/code>instead.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/02\/16\/oranges.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[[2,1,1],[1,1,0],[0,1,1]]\n<strong>Output: <\/strong>4\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[[2,1,1],[0,1,1],[1,0,1]]\n<strong>Output: <\/strong>-1\n<strong>Explanation: <\/strong> The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>[[0,2]]\n<strong>Output: <\/strong>0\n<strong>Explanation: <\/strong> Since there are already no fresh oranges at minute 0, the answer is just 0.\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>1 &lt;= grid.length &lt;= 10<\/code><\/li><li><code>1 &lt;= grid[0].length &lt;= 10<\/code><\/li><li><code>grid[i][j]<\/code>&nbsp;is only&nbsp;<code>0<\/code>,&nbsp;<code>1<\/code>, or&nbsp;<code>2<\/code>.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:&nbsp;BFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(mn)<br>Space complexity: O(mn)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, Running time: 12 ms, 10.8 MB\nclass Solution {\npublic:\n  int orangesRotting(vector<vector<int>>& grid) {\n    const int m = grid.size();\n    const int n = grid[0].size();\n    queue<pair<int,int>> q;\n    int fresh = 0;\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        if (grid[i][j] == 1) ++fresh;\n        else if (grid[i][j] == 2) q.emplace(j, i);\n    vector<int> dirs = {1, 0, -1, 0, 1};    \n    int days = 0;\n    while (!q.empty() && fresh) {\n      int size = q.size();\n      while (size--) {\n        int x = q.front().first;\n        int y = q.front().second;\n        q.pop();\n        for (int i = 0; i < 4; ++i) {\n          int dx = x + dirs[i];\n          int dy = y + dirs[i + 1];\n          if (dx < 0 || dx >= n || dy < 0 || dy >= m || grid[dy][dx] != 1) continue;\n          --fresh;\n          grid[dy][dx] = 2;\n          q.emplace(dx, dy);\n        }\n      }\n      ++days;\n    }    \n    return fresh ? -1 : days;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a given grid, each cell can have one of three&nbsp;values: the value&nbsp;0&nbsp;representing an empty cell; the value&nbsp;1&nbsp;representing a fresh orange; the value&nbsp;2&nbsp;representing a rotten&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[34,222,278],"class_list":["post-4862","post","type-post","status-publish","format-standard","hentry","category-searching","tag-bfs","tag-easy","tag-grid","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4862","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4862"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4862\/revisions"}],"predecessor-version":[{"id":4865,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4862\/revisions\/4865"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4862"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4862"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4862"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}