diff options
-rw-r--r-- | flood_fill.c | 66 | ||||
-rw-r--r-- | flood_fill.py | 37 |
2 files changed, 103 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); +} diff --git a/flood_fill.py b/flood_fill.py new file mode 100644 index 0000000..0f34f29 --- /dev/null +++ b/flood_fill.py @@ -0,0 +1,37 @@ +# 733. Flood Fill + +""" +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 +""" + + +class Solution(object): + def floodFill(self, image, sr, sc, color): + """ + :type image: List[List[int]] + :type sr: int + :type sc: int + :type color: int + :rtype: List[List[int]] + """ + n, m, old = len(image), len(image[0]), image[sr][sc] + + def dfs(r, c): + if (not (0 <= r < n and 0 <= c < m)) or image[r][c] != old: + return + image[r][c] = color + [dfs(r + x, c + y) for (x, y) in ((0, 1), (1, 0), (0, -1), (-1, 0))] + + if old != color: + dfs(sr, sc) + return image + + +if __name__ == "__main__": + obj = Solution() + print(obj.floodFill(image=[[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr=1, sc=1, color=2)) + print(obj.floodFill(image=[[0, 0, 0], [0, 0, 0]], sr=0, sc=0, color=0)) |