Flood Fill Algorithm
Problem-Given a 2D matrix,location of a point and a variable k.Our task is to change the value of given location and its adjacent position(except diagonals) having same values as that of given location with the variable k.
Approach-problem can easily be solved by using DFS in Graph.Make a function which takes input of location.Change the color of it and then recursively call the function for its adjascent sides.
//Code starts here
using namespace std;
const int M = 100,
N = 100;
int a[M][N];
int m, n;
void floodfill(int x, int y, int old, int newc) {
if (x >= m || y >= n || x < 0 || y < 0) {
return;
}
if (a[x][y] == old) {
a[x][y] = newc;
floodfill(x + 1, y, old, newc);
floodfill(x, y + 1, old, newc);
floodfill(x - 1, y, old, newc);
floodfill(x, y - 1, old, newc);
}
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
int x, y, k, old;
cin >> x >> y >> k;
old = a[x][y];
floodfill(x, y, old, k);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << a[i][j] << " ";
}
//cout<<endl;
}
cout << endl;
}
return 0;
}
//code ends here
Input:
3
3 4
0 1 1 0 1 1 1 1 0 1 2 3
0 1 5
2 2
1 1 1 1
0 1 8
4 4
1 2 3 4 1 2 3 4 1 2 3 4 1 3 2 4
0 2 9
Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8
1 2 9 4 1 2 9 4 1 2 9 4 1 3 2 4
Comments