diff options
Diffstat (limited to 'flood_fill.c')
-rw-r--r-- | flood_fill.c | 66 |
1 files changed, 66 insertions, 0 deletions
diff --git a/flood_fill.c b/flood_fill.c new file mode 100644 index 0000000..f01f66d --- /dev/null +++ b/flood_fill.c @@ -0,0 +1,66 @@ +// 733. Flood Fill +#include "leetcode.h" + +/* + * you are given an image represented by an 'm x n' grid of integers 'image', + * where 'image[i][j]' represents the pixel value of the image. you are also + * given three integers 'sr', 'sc', and 'color'. your task is to perform a flood + * fill on the image starting from the pixel 'image[sr][sc]'. return the + * modified image after performing the flood fill + */ + +void dfs(int **image, int imageSize, int *imageColSize, int sr, int sc, int new, + int old) { + if (sr < 0 || sr >= imageSize) + return; + if (sc < 0 || sc >= imageColSize[0]) + return; + if (image[sr][sc] == old) { + image[sr][sc] = new; + dfs(image, imageSize, imageColSize, sr - 1, sc, new, old); + dfs(image, imageSize, imageColSize, sr + 1, sc, new, old); + dfs(image, imageSize, imageColSize, sr, sc - 1, new, old); + dfs(image, imageSize, imageColSize, sr, sc + 1, new, old); + } +} + +int **floodFill(int **image, int imageSize, int *imageColSize, int sr, int sc, + int color, int *returnSize, int **returnColumnSizes) { + int i; + *returnSize = imageSize; + *returnColumnSizes = (int *)malloc(imageSize * sizeof(int)); + for (int i = 0; i < imageSize; i++) + (*returnColumnSizes)[i] = imageColSize[i]; + if (color != image[sr][sc]) + dfs(image, imageSize, imageColSize, sr, sc, color, image[sr][sc]); + return image; +} + +int main() { + int i1i[3][3] = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}, + i2i[2][3] = {{0, 0, 0}, {0, 0, 0}}; + struct two_d_arr i1, i2; + two_d_arr_init(&i1, ARRAY_SIZE(i1i), ARRAY_SIZE(i1i[0]), i1i); + two_d_arr_init(&i2, ARRAY_SIZE(i2i), ARRAY_SIZE(i2i[0]), i2i); + int rs1, rs2, *rcs1, *rcs2; + int **ff1 = floodFill(i1.arr, i1.row_size, i1.col_size, 1, 1, 2, &rs1, &rcs1); + int **ff2 = floodFill(i2.arr, i2.row_size, i2.col_size, 0, 0, 0, &rs2, &rcs2); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", ff1[i][j]); // expect: [[2,2,2],[2,2,0],[2,0,1]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", ff2[i][j]); // expect: [[0,0,0],[0,0,0]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(ff1[i]); + free(ff1), free(rcs1); + for (int i = 0; i < rs2; i++) + free(ff2[i]); + free(ff2), free(rcs2); +} |