Hà Phan（河）

Flood Fill

An `image` is represented by a 2-D array of integers, each integer representing the pixel value of the image (from `0` to `65535`).

Given a coordinate `(sr, sc)` representing the starting pixel (row and column) of the flood fill, and a pixel value `newColor`, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the `newColor`.

At the end, return the modified image.

Example 1:

``````Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
``````

Note:

• The length of `image` and `image[0]` will be in the range `[1, 50]`.
• The given starting pixel will satisfy `0 <= sr < image.length` and `0 <= sc < image[0].length`.
• The value of each color in `image[i][j]` and `newColor` will be an integer in `[0, 65535]`.

## Solution

Using preOrder traverse

``````class Solution {
func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ newColor: Int) -> [[Int]] {
var map = image
fill(Point(r: sr, c: sc)
, map: &map
, initColor: image[sr][sc]
, newColor: newColor)
return map
}

func fill(_ p: Point, map: inout [[Int]], initColor: Int, newColor: Int) {
guard p.isValid(&map) else { return }
guard map[p.r][p.c] != newColor else { return }
guard map[p.r][p.c] == initColor else { return }

map[p.r][p.c] = newColor

fill(p.top, map: &map, initColor: initColor, newColor: newColor)
fill(p.left, map: &map, initColor: initColor, newColor: newColor)
fill(p.bottom, map: &map, initColor: initColor, newColor: newColor)
fill(p.right, map: &map, initColor: initColor, newColor: newColor)
}

struct Point {
var r: Int
var c: Int

var top: Point {
return Point(r: r - 1, c: c)
}
var bottom: Point {
return Point(r: r + 1, c: c)
}
var left: Point {
return Point(r: r, c: c - 1)
}
var right: Point {
return Point(r: r, c: c + 1)
}

func isValid(_ map: inout [[Int]]) -> Bool {
guard r > -1, r < map.count, c > -1, c < map[0].count else{
return false
}
return true
}
}
}
``````