-
Notifications
You must be signed in to change notification settings - Fork 0
/
floodfill_theory.py
112 lines (92 loc) · 3.76 KB
/
floodfill_theory.py
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
# -*- coding: utf-8 -*-
"""
@author : zenithude
Flood fill Algorithm – how to implement fill() in paint?
In MS-Paint, when we take the brush to a pixel and click, the color of the
region of that pixel is replaced with a new selected color. Following is the
problem statement to do this task. Given a 2D screen, location of a pixel in
the screen and a color, replace color of the given pixel and all adjacent
same colored pixels with the given color.
Example:
Input:
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
x = 4, y = 4, newColor = 3
The values in the given 2D screen indicate colors of the pixels.
x and y are coordinates of the brush, newColor is the color that
should replace the previous color on screen[x][y] and all surrounding
pixels with same color.
Output:
Screen should be changed to following.
screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1},
};
Recommended: Please solve it on “PRACTICE ” first, before moving on to the
solution.
Flood Fill Algorithm: The idea is simple, we first replace the color of
current pixel, then recur for 4 surrounding points. The following is
detailed algorithm.
// A recursive function to replace previous color 'prevC' at '(x, y)'
// and all surrounding pixels of (x, y) with new color 'newC' and
floodFil(screen[M][N], x, y, prevC, newC)
1) If x or y is outside the screen, then return.
2) If color of screen[x][y] is not same as prevC, then return
3) Recur for north, south, east and west.
floodFillUtil(screen, x+1, y, prevC, newC);
floodFillUtil(screen, x-1, y, prevC, newC);
floodFillUtil(screen, x, y+1, prevC, newC);
floodFillUtil(screen, x, y-1, prevC, newC);
"""
# Python3 program to implement
# flood fill algorithm
# Dimentions of paint screen
M = 8
N = 8
# A recursive function to replace
# previous color 'prevC' at '(x, y)'
# and all surrounding pixels of (x, y)
# with new color 'newC' and
def floodFillUtil(screen, x, y, prevC, newC):
# Base cases
if (x < 0 or x >= M or y < 0 or y >= N or screen[x][y] != prevC or
screen[x][y] == newC):
return
# Replace the color at (x, y)
screen[x][y] = newC
# Recur for north, east, south and west
floodFillUtil(screen, x + 1, y, prevC, newC)
floodFillUtil(screen, x - 1, y, prevC, newC)
floodFillUtil(screen, x, y + 1, prevC, newC)
floodFillUtil(screen, x, y - 1, prevC, newC)
# It mainly finds the previous color on (x, y) and
# calls floodFillUtil()
def floodFill(screen, x, y, newC):
prevC = screen[x][y]
floodFillUtil(screen, x, y, prevC, newC)
# Driver Code
screen = [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 1, 1], [1, 2, 2, 2, 2, 0, 1, 0],
[1, 1, 1, 2, 2, 0, 1, 0], [1, 1, 1, 2, 2, 2, 2, 0],
[1, 1, 1, 1, 1, 2, 1, 1], [1, 1, 1, 1, 1, 2, 2, 1]]
x = 4
y = 4
newC = 3
floodFill(screen, x, y, newC)
print("Updated screen after call to floodFill:")
for i in range(M):
for j in range(N):
print(screen[i][j], end=' ')
print()