diff options
Diffstat (limited to 'rotting_oranges.c')
-rw-r--r-- | rotting_oranges.c | 86 |
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); +} |