Flood fill Algorithm
PROBLEM :
Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.
Output:
For each test case print the space separated values of the new matrix.
Constraints:
1<=T<=10
1<=M[][]<=100
Example:
Input:
2
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
Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
#define MAX 100
void FloodFill(int screen[MAX][MAX],int ,int ,int ,int ,int ) ;
void UtilFloodFill(int screen[MAX][MAX],int ,int ,int ,int ,int ,int ) ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int n,m ;
cin>>n>>m ;
int screen[MAX][MAX] ;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>screen[i][j] ;
int x,y,k ;
cin>>x>>y>>k ;
FloodFill(screen,n,m,x,y,k) ;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cout<<screen[i][j]<<" " ;
cout<<endl ;
}
return 0;
}
void FloodFill(int screen[MAX][MAX],int n,int m,int x,int y,int k)
{
int oldC=screen[x][y] ;
UtilFloodFill(screen,n,m,x,y,oldC,k) ;
}
void UtilFloodFill(int screen[MAX][MAX],int n,int m,int x,int y,int oldC,int newC)
{
if(x<0||x>=n||y<0||y>=m)
return ;
if(screen[x][y]!=oldC)
return ;
screen[x][y]=newC ;
UtilFloodFill(screen,n,m,x-1,y,oldC,newC) ;
UtilFloodFill(screen,n,m,x+1,y,oldC,newC) ;
UtilFloodFill(screen,n,m,x,y-1,oldC,newC) ;
UtilFloodFill(screen,n,m,x,y+1,oldC,newC) ;
}
--------------------------------------------------------------------------------
Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.
Output:
For each test case print the space separated values of the new matrix.
Constraints:
1<=T<=10
1<=M[][]<=100
Example:
Input:
2
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
Output:
0 5 5 0 5 5 5 5 0 5 2 3
8 8 8 8
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
#define MAX 100
void FloodFill(int screen[MAX][MAX],int ,int ,int ,int ,int ) ;
void UtilFloodFill(int screen[MAX][MAX],int ,int ,int ,int ,int ,int ) ;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int n,m ;
cin>>n>>m ;
int screen[MAX][MAX] ;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>screen[i][j] ;
int x,y,k ;
cin>>x>>y>>k ;
FloodFill(screen,n,m,x,y,k) ;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cout<<screen[i][j]<<" " ;
cout<<endl ;
}
return 0;
}
void FloodFill(int screen[MAX][MAX],int n,int m,int x,int y,int k)
{
int oldC=screen[x][y] ;
UtilFloodFill(screen,n,m,x,y,oldC,k) ;
}
void UtilFloodFill(int screen[MAX][MAX],int n,int m,int x,int y,int oldC,int newC)
{
if(x<0||x>=n||y<0||y>=m)
return ;
if(screen[x][y]!=oldC)
return ;
screen[x][y]=newC ;
UtilFloodFill(screen,n,m,x-1,y,oldC,newC) ;
UtilFloodFill(screen,n,m,x+1,y,oldC,newC) ;
UtilFloodFill(screen,n,m,x,y-1,oldC,newC) ;
UtilFloodFill(screen,n,m,x,y+1,oldC,newC) ;
}
--------------------------------------------------------------------------------
Comments
Post a Comment