【第三轮】8.3-8.9 CareerCup 9.7

9.7 Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors),
a point, and a new color, fill in the surrounding area until the color changes from the original color.




回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
depth first search
for each pixel which need to be changed color, search its four neighbors


【时间复杂度】
O(mn)


【空间复杂度】
O(mn)


【gist link】
https://gist.github.com/happyWinner/3e03b08e8c394bdfdb4d

【解题思路】
Start from the point, recursively trying to fill in both four directions
* check if the point is valid(not out of range)
* check if color is same as the color we want to change from.
* track where is the previous position prevent back tracking

【时间复杂度】
O(X*Y)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/cc3970a0f22c06443b08

【解题思路】
Start from the input point,
1. check if the point in the screen (x,y range)
2. check if the point match the old color
return if the point does not qualify
change the point's color
move to the 4 directions
【时间复杂度】
O(M*N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bitcpf/7b984da0cdb9b34de7a5