1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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);
}
|