aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--rotting_oranges.c86
-rw-r--r--rotting_oranges.py51
2 files changed, 137 insertions, 0 deletions
diff --git a/rotting_oranges.c b/rotting_oranges.c
new file mode 100644
index 0000000..f59eff9
--- /dev/null
+++ b/rotting_oranges.c
@@ -0,0 +1,86 @@
+// 994. Rotting Oranges
+#include "leetcode.h"
+
+/*
+ * 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-directionall adjacent to a rotten orange becomes rotten. return the minimum
+ * number of minutethat must elapse until no cell has a fresh oragne. if this is
+ * impossible, return -1
+ */
+
+int orangesRotting(int **grid, int gridSize, int *gridColSize) {
+ int min_val = 0, **dp = (int **)malloc(gridSize * sizeof(int *));
+ for (int i = 0; i < gridSize; i++)
+ dp[i] = (int *)malloc((*gridColSize) * sizeof(int));
+ int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, dir_row = 4;
+ bool searching = true;
+ while (searching) {
+ bool transition = false, check = false;
+ for (int i = 0; i < gridSize; i++) {
+ for (int j = 0; j < (*gridColSize); j++) {
+ if (dp[i][j] == min_val)
+ continue;
+ if (grid[i][j] == 2) {
+ dp[i][j] = min_val;
+ for (int k = 0; k < dir_row; k++) {
+ int i_adj = i + dir[k][0], j_adj = j + dir[k][1];
+ if (i_adj >= 0 && i_adj < gridSize && j_adj >= 0 &&
+ j_adj < *gridColSize) {
+ if (grid[i_adj][j_adj] == 1) {
+ grid[i_adj][j_adj] = 2;
+ dp[i_adj][j_adj] = min_val;
+ transition = true;
+ }
+ }
+ }
+ } else if (grid[i][j] == 1) {
+ check = true;
+ bool connect = false;
+ for (int k = 0; k < dir_row; k++) {
+ int i_adj = i + dir[k][0], j_adj = j + dir[k][1];
+ if (i_adj >= 0 && i_adj < gridSize && j_adj >= 0 &&
+ j_adj < (*gridColSize)) {
+ if (grid[i_adj][j_adj] == 1 || grid[i_adj][j_adj] == 2) {
+ connect = true;
+ break;
+ }
+ }
+ }
+ if (!connect)
+ return -1;
+ }
+ }
+ }
+ if (check) {
+ if (transition)
+ searching = true;
+ else
+ return -1;
+ } else
+ searching = false;
+ if (transition)
+ min_val++;
+ }
+ for (int i = 0; i < gridSize; i++)
+ free(dp[i]);
+ free(dp);
+ return min_val;
+}
+
+int main() {
+ int g1i[3][3] = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}},
+ g2i[3][3] = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}, g3i[1][2] = {{0, 2}};
+ struct two_d_arr g1, g2, g3;
+ two_d_arr_init(&g1, 3, 3, g1i);
+ two_d_arr_init(&g2, 3, 3, g2i);
+ two_d_arr_init(&g3, 1, 2, g3i);
+ printf("%d\n", orangesRotting(g1.arr, g1.row_size, g1.col_size)); // expect: 4
+ printf("%d\n", orangesRotting(g2.arr, g2.row_size, g2.col_size)); // expect:
+ // -1
+ printf("%d\n", orangesRotting(g3.arr, g3.row_size, g3.col_size)); // expect: 0
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+ two_d_arr_free(&g3);
+}
diff --git a/rotting_oranges.py b/rotting_oranges.py
new file mode 100644
index 0000000..7d1fc5f
--- /dev/null
+++ b/rotting_oranges.py
@@ -0,0 +1,51 @@
+# 994. Rotting Oranges
+from collections import deque
+
+"""
+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-directionall adjacent to a rotten orange becomes rotten. return the minimum
+number of minutethat must elapse until no cell has a fresh oragne. if this is
+impossible, return -1
+"""
+
+
+class Solution(object):
+ def orangesRotting(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ rows = len(grid)
+ if rows == 0:
+ return -1
+ cols, fresh_cnt, rotten = len(grid[0]), 0, deque()
+ for r in range(rows):
+ for c in range(cols):
+ if grid[r][c] == 2:
+ rotten.append((r, c))
+ elif grid[r][c] == 1:
+ fresh_cnt += 1
+ min_pass = 0
+ while rotten and fresh_cnt > 0:
+ min_pass += 1
+ for _ in range(len(rotten)):
+ x, y = rotten.popleft()
+ for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
+ xx, yy = x + dx, y + dy
+ if xx < 0 or xx == rows or yy < 0 or yy == cols:
+ continue
+ if grid[xx][yy] == 0 or grid[xx][yy] == 2:
+ continue
+ fresh_cnt -= 1
+ grid[xx][yy] = 2
+ rotten.append((xx, yy))
+ return min_pass if fresh_cnt == 0 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.orangesRotting(grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
+ print(obj.orangesRotting(grid=[[2, 1, 1], [0, 1, 1], [1, 0, 1]]))
+ print(obj.orangesRotting(grid=[[0, 2]]))