CareerCup

flood fill algo.
was asked same question in google years back.

It can be done with recursion. Just check for adjacent elements while also keeping track of out of bounds of array. Here is the code. You can test it:

#include <stdio.h>
#include <stdlib.h>

void convertToNextColor(char arr[4][6],int i,int j)
{
    if(i<0||j<0)
        return;
    else if(i>5||j>5)
        return;
    else
    {
        if(arr[i][j]=='B')
        {
            convertToNextColor(arr,i,j-1);
            arr[i][j]='W';
            convertToNextColor(arr,i,j+1);
            arr[i][j]='W';
            convertToNextColor(arr,i-1,j);
            arr[i][j]='W';
            convertToNextColor(arr,i+1,j);
            arr[i][j]='W';
        }
        else
            return;
    }
}
int main()
{
    char a[4][6]={{'W','B','W','W','B','W'},{'B','B','W','W','B','W'},{'W','B','B','B','W','B'},{'W','B','W','W','B','B'}};
    int i,j;
    convertToNextColor(a,1,1);
    for(i=0;i<4;i++)
    {
        for(j=0;j<6;j++)
            printf(" %c ",a[i][j]);
        printf("\n");
    }
}

So what's exactly is required yo be done?

That's the simple flood fill algo, for which the iterative implementation is given below:

#include <stdio.h>
#include <queue>
#include <vector>

using std::queue;
using std::vector;

typedef vector<int> ivec;
typedef vector<ivec> itab;

struct coord {
    int x;
    int y;
    coord(int cx, int cy) : x(cx), y(cy) {};
};

void print(const itab& tab)
{
    for (int j = 0; j < tab.size(); ++j){
        int cc = tab[j].size();
        for (int i = 0; i < cc; ++i){
            printf("%-3d ", tab[j][i]);
        }
        printf("\n");
    }
}

void init_table(int* dat, int cy, int cx, itab& tab)
{
    tab.resize(cy);
    
    for (int j = 0; j < cy; ++j){
        tab[j].resize(cx);
        
        for (int i = 0; i < cx; ++i){
            ;//tab
            int v = dat[j * cx + i];
            //printf("%d ", v);
            
            tab[j][i] = v;
        }
    }
}

void flood_fill(itab& dat, int py, int px, int color)
{
    int rc, cc;
    if (dat.size() == 0)
        return;
    if (dat[0].size() == 0)
        return;
    
    rc = dat.size();
    cc = dat[0].size();
    
    if (px < 0 || px >= cc)
        return;
    if (py < 0 || py >= rc)
    return;

    int val = dat[py][px];
    
    std::queue<coord> q;
    q.push(coord(px, py));
    
    while(!q.empty()){
        coord c = q.front();
        q.pop();
        
        dat[c.y][c.x] = color;
        // now add the neighbours of this cell to the queue
        // if the neighbour has the same color as this cell
        if (c.x - 1 > 0 && dat[c.y][c.x - 1] == val)
            q.push(coord(c.x - 1, c.y));

        if (c.x + 1 < cc && dat[c.y][c.x + 1] == val)
            q.push(coord(c.x + 1, c.y));
            
        if (c.y - 1 > 0 && dat[c.y - 1][c.x] == val)
            q.push(coord(c.x, c.y - 1));

        if (c.y + 1 < rc && dat[c.y + 1][c.x] == val)
            q.push(coord(c.x, c.y + 1));
            
    }    
}

int main()
{
    int dat[] = {
                  1,  1,  3,  4,
                  5,  1,  1,  8,
                  9,  1,  10,  12,
                  13, 1,  4,  16,
                  17, 1,  1,  1
                  };
                  
    itab tab;
    init_table(dat, 5, 4, tab);
    print(tab);
    
    printf("\n===============\n");
    
    flood_fill(tab, 0, 0, 0);
    print(tab);
    
    return 0;
}

Output:

1   1   3   4
5   1   1   8
9   1   10  12
13  1   4   16
17  1   1   1

===============
0   0   3   4
5   0   0   8
9   0   10  12
13  0   4   16
17  0   0   0

All the neighbours of the pixel (x,y) selected have to be changed including the current pixel.
There are 8 neighbours for a pixel.
(x-1, y-1)
(x-1, y)
(x-1, y+1)
(x, y-1)
(x, y+1)
(x+1, y-1)
(x+1, y)
(x+1, y+1)
for all these pixels the color will be the same as the new color of the clicked pixel at (x,y)

Here's my implementation of the algorithm. I used the recursive approach since it's much easier to understand. It is important to change the value in cell (i,j) BEFORE diving into the recursive calls, because if not you can end up with infinite recursive calls. Here's the C++ implementation:

#include <iostream>

using namespace std;

void PrintMat(int ** matrix, int height, int width)
{
	for(int r = 0; r < height;r++)
	{
		for(int c = 0; c < width;c++)
			cout<<matrix[r][c]<<" ";

		cout<<endl;
	}
}


void ChangeColor(int & val)
{
	if(val==1)
		val = 0;
	else
		val = 1;
}

void ChangePixels(int ** matrix, int rows, int cols, int r, int c)
{
	if(r<0 || r >= rows || c<0 || c>=cols)
		return;

	int val = matrix[r][c];
		
	ChangeColor(matrix[r][c]);

	if(r>0 && val == matrix[r-1][c])
		ChangePixels(matrix, 5, 5, r-1, c);
	
	if(r<rows-1 && val == matrix[r+1][c])
		ChangePixels(matrix, 5, 5, r+1, c);
	
	if(c>0 && val == matrix[r][c-1])
		ChangePixels(matrix, 5, 5, r, c-1);
	
	if(c<cols-1 && val == matrix[r][c+1])
		ChangePixels(matrix, 5, 5, r, c+1);
}	

void main(void)
{
	int **matrix = new int*[5];
	int height = 5;
	int width = 5;


	int a[] = { 0, 1, 0, 0, 0};
	int b[] = { 0, 1, 0, 1, 1};	
	int c[] = { 1, 1, 0, 0, 1};	
	int d[] = { 0, 1, 1, 0, 1};	
	int e[] = { 0, 1, 0, 0, 1};	

	matrix[0] = a;
	matrix[1] = b;
	matrix[2] = c;
	matrix[3] = d;
	matrix[4] = e;

	ChangePixels(matrix, 5, 5, 2, 1);

	PrintMat(matrix, 5, 5);
}

This was great ... Flood fill algorithm .. hmm

i came with a totally different approach but I think it will work well though.
Can anybody comment about my approach.
Make each entry as a vertex in graph and make its adjacent elements as adjacent nodes.
Algorithm:
Push the clicked vertex to the queue.

while(queue not empty)
pop the element from queue
push the adj nodes which are only B in to the queue (and toggle their color)

flood fill algorithm....its beautiful..

{{//first we need to check what the color is at a particular index..

void colorat(int *matrix[], int m, int n, int x, int y) //m, n are dimensions of the matrix, and x,y is //the current position
{
if(x<=0 || x>=m) return ;
if(y<=0 || y>=n ) return;

char color = matrix[x][y];

changecolor(matrix, x-1,y-1, color);
changecolor(matrix, x,y-1, color);
changecolor(matrix, x+1,y-1, color);
changecolor(matrix, x-1,y, color);
changecolor(matrix, x+1,y, color);
changecolor(matrix, x-1,y+1, color);
changecolor(matrix, x,y+1, color);
changecolor(matrix, x+1,y-1, color);

}

void changecolor(int *matrix[], int x, int y, char color)
{
if(matrix[i][j]!=color)
{
matrix[i][j]=color;
}
else return;
}


}}

package com.zhuyu_deng.test;

import java.util.Stack;

public class Test
{

	private static void printMatrix(char[][] a)
	{
		for (int i = 0; i < a.length; ++i)
		{
			for (int j = 0; j < a[i].length; ++j)
			{
				System.out.print(a[i][j] + "  ");
			}
			System.out.println();
		}
	}
	
	private static void floodFill(char[][] a, int x, int y)
	{
		class Node
		{
			public Node(int x, int y)
			{
				this.x = x;
				this.y = y;
			}

			int x;
			int y;
		}

		char orgColor = a[x][y];
		char revColor = a[x][y] == 'W' ? 'B' : 'W';
		int size = 0;
	
		Node stack[] = new Node[a.length * a[0].length];
		stack[size] = new Node(x, y);
		while (size >= 0)
		{
			Node cur = stack[size];
			size--;
			a[cur.x][cur.y] = revColor;
			if (cur.x - 1 >= 0 && orgColor == a[cur.x - 1][cur.y])
			{
				stack[++size] = (new Node(cur.x-1, cur.y));
			}
			if (cur.x + 1 < a.length && orgColor == a[cur.x + 1][cur.y])
			{
				stack[++size] = (new Node(cur.x+1, cur.y));
			}
			if (cur.y - 1 >= 0 && orgColor == a[cur.x][cur.y - 1])
			{
				stack[++size] = (new Node(cur.x, cur.y-1));
			}
			if (cur.y + 1 < a[0].length && orgColor == a[cur.x][cur.y + 1])
			{
				stack[++size] = (new Node(cur.x, cur.y + 1));
			}
		}
		
	}

	public static void main(String args[])
	{
		// int[] a = {-2,11,-4,13,-5,-2};
		int[][] b = { { 0, -2, -7, 0 }, { 9, 2, -6, 2 }, { -4, 1, -4, 1 },
				{ -1, 8, 0, -2 } };
		int[][] matrix = { { 2, 3, 4, 1 }, { 1, 1, 3, 9 }, { 2, 2, 3, 1 },
				{ 2, 2, 3, 1 } };
		char a[][] = new char[][] { { 'W', 'B', 'W', 'W', 'B', 'W' },
				{ 'B', 'B', 'W', 'W', 'B', 'W' },
				{ 'W', 'B', 'B', 'B', 'W', 'B' },
				{ 'W', 'B', 'W', 'W', 'B', 'B' } };
		
		
		printMatrix(a);

		floodFill(a, 2, 2);

		System.out.println();

		printMatrix(a);
		
	}
}

import java.util.*;

public class Fill {

	public static void print(char[][] a) {
		System.out.println();
		System.out.print(a[0].length);
		for (char[] l : a) {
			for (char c : l) {
				System.out.print(c + " ");
			}
			System.out.println();
		}
	}
	
	public static ArrayList<Point> checkAdj(char[][] a, int i, int j) {
		ArrayList<Point> ps = new ArrayList<Point>();
		char c = a[i][j];
		
		int curI = i-1; int curJ = j;
		if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a[0].length && (a[curI][curJ] == c))
			ps.add(new Point(curI, curJ));
			
		curI = i+1; curJ = j;
		if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a[0].length && (a[curI][curJ] == c))
			ps.add(new Point(curI, curJ));
		
		curI = i; curJ = j-1;	
		if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a[0].length && (a[curI][curJ] == c))
			ps.add(new Point(curI, curJ));
		
		curI = i; curJ = j+1;
		if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a[0].length && (a[curI][curJ] == c))
			ps.add(new Point(curI, curJ));
		
		
		return ps;
	}
	
	public static void fill(char[][] a, int i, int j, char f) {
		
		// check adjacent pixels
		ArrayList<Point> ps = checkAdj(a, i, j);
		// 
		a[i][j] = f;
		
		for (Point p: ps) {
			fill(a, p.i, p.j, f);
		}	
	}
	
	public static void main (String[] args) throws FileNotFoundException {
		char a[][] = new char[][] { { 'W', 'B', 'W', 'W', 'B', 'W' },
				{ 'B', 'B', 'W', 'W', 'B', 'W' },
				{ 'W', 'B', 'B', 'B', 'W', 'B' },
				{ 'W', 'B', 'W', 'W', 'B', 'B' } };
		print(a);
		fill(a, 1, 1, 'L');
		print(a);
	}	
}

class Point{
	int i;
	int j;
	
	Point(int i, int j) {this.i = i; this.j = j;}
}

I think BFS can do the job as well. Pass the node that is recently clicked to the BFS as the starting node and then do a simple BFS walk onward. We should keep the previous color of the recently clicked node in a temporary variable, say prevColor. In the main loop of the BFS we should do something like:

while(!emptyStack())
{
ClickedNode=pop();
for(i=0;i<N;i++)
{
if(graph[ClickedNode][i]!=inf && color[i]==prevColor)
{
parent[i]=ClickedNode;
color[i]=NewColor; //i.e., ~prevColor
push(i);
}
}
}

Please correct me if there is a mistake in the above approach.

A solution in Python:

W = 0
B = 1

def f(A, r, c, dir=None):
		
	Nr = len(A)
	Nc = len(A[0])
	
	type = A[r][c]
	A[r][c] = W if type == B else B
	
	if dir!='L' and (c+1 < Nc):
		if A[r][c+1] == type: f(A, r, c+1, dir='R')
	
	if dir!='R' and (c-1 >= 0):
		if A[r][c-1] == type: f(A, r, c-1, dir='L')
	
	if dir!='U' and (r+1 < Nr):
		if A[r+1][c] == type: f(A, r+1, c, dir='D')
	
	if dir!='D' and (r-1 >= 0):
		if A[r-1][c] == type: f(A, r-1, c, dir='U')
	
	
A = [[W,B,W,W,B,W],
	 [B,B,W,W,B,W],
	 [W,B,B,B,W,B],
	 [W,B,W,W,B,B]]
	 
f(A, 2, 2)
for row in A:
	print row

A solution in Python:

W = 0
B = 1

def f(A, r, c, dir=None):
		
	Nr = len(A)
	Nc = len(A[0])
	
	type = A[r][c]
	A[r][c] = W if type == B else B
	
	if dir!='L' and (c+1 < Nc):
		if A[r][c+1] == type: f(A, r, c+1, dir='R')
	
	if dir!='R' and (c-1 >= 0):
		if A[r][c-1] == type: f(A, r, c-1, dir='L')
	
	if dir!='U' and (r+1 < Nr):
		if A[r+1][c] == type: f(A, r+1, c, dir='D')
	
	if dir!='D' and (r-1 >= 0):
		if A[r-1][c] == type: f(A, r-1, c, dir='U')
	
	
A = [[W,B,W,W,B,W],
	 [B,B,W,W,B,W],
	 [W,B,B,B,W,B],
	 [W,B,W,W,B,B]]
	 
f(A, 2, 2)
for row in A:
	print row

So I am assuming this is simply how to make the pixels change color and there is no end goal (like turn the screen from black to white and count the number of clicks).

1. Initialize 2D array with 0's to represent color 1.
2. Initialize mouse event handler that returns point x,y on mouse click
3. Return x,y to the colorChange function
4. colorChange then flips pixels: (x,y) (x-1,y) (x+1,y) (x,y-1) (x,y+1) to the opposite value (0's to 1's, and 1's back to 0's) as long as their current value matches the value at x,y.
4a. You must utilize edge/corner checking to make sure you do not encounter ArrayOutOfBounds Exceptions.