aboutsummaryrefslogtreecommitdiff
path: root/rotting_oranges.c
diff options
context:
space:
mode:
Diffstat (limited to 'rotting_oranges.c')
-rw-r--r--rotting_oranges.c86
1 files changed, 86 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);
+}