#include <iostream>

namespace {

void floodFill( int ** image, int sizeX, int sizeY, int targetColor, int newColor, int x, int y );

void floodFillInternal( int ** image, bool ** visited,
                                   int sizeX, int sizeY,
                                   int targetColor, int newColor, int x, int y );
void print(int ** image, int sizeX, int sizeY);

}

int main(int argc, char** argv)
{
	std::cout << "Starting execution" << std::endl;
	int sizeX = 3;
	int sizeY = 4;
	int* image[sizeX];
	for(int i = 0 ; i < sizeX ; i++)
	{
		image[i] = new int[sizeY];
	}

	image[0][2] = 4;
	image[1][2] = 4;

	print(image, sizeX, sizeY);
	floodFill(image, sizeX, sizeY, 0, 2, 0, 0 );
	print(image, sizeX, sizeY);
	std::cout << "Done" << std::endl;

	for(int i = 0 ; i < sizeX ; i++)
		delete[] image[i];
}

namespace {

void floodFill( int ** image, int sizeX, int sizeY, int targetColor, int newColor, int x, int y )
{
	// Check target point is between boundaries
	if ( x > sizeX -1 || x < 0 )
		return;
	if ( y > sizeY-1 || y < 0 )
		return;

	// Initialize visited
	bool * visited[ sizeX ];
	for( int i = 0 ; i < sizeX ; i++ ) {
		visited[i] = new bool[sizeY];
	}

	// Start recursing
	floodFillInternal(image, visited, sizeX, sizeY, targetColor, newColor, x, y);

	// Free the visited structure
	for( int i = 0 ; i < sizeX ; i++ ) {
		delete[] visited[i];
	}
}

void floodFillInternal( int ** image, bool ** visited,
                                   int sizeX, int sizeY,
                                   int targetColor, int newColor, int x, int y )
{
	// Check target point is between boundaries
	if ( x > sizeX -1 || x < 0 )
		return;
	if ( y > sizeY-1 || y<0 )
		return;

	if ( image[x][y] != targetColor || visited[x][y])
		return;

	image[x][y] = newColor;
	visited[x][y] = 1;
	floodFillInternal(image, visited, sizeX, sizeY, targetColor, newColor, x+1, y);
	floodFillInternal(image, visited, sizeX, sizeY, targetColor, newColor, x-1, y);
	floodFillInternal(image, visited, sizeX, sizeY, targetColor, newColor, x, y+1);
	floodFillInternal(image, visited, sizeX, sizeY, targetColor, newColor, x, y-1);
}

void print(int ** image, int sizeX, int sizeY)
{
	std::cout << "[" << std::endl;
	for( int i = 0; i < sizeY ; ++i)
	{
		for(int j = 0 ; j < sizeX ; ++j)
		{
			std::cout << image[j][i] << " , ";
		}
		std::cout << std::endl;
	}
	std::cout << "]" << std::endl;
}
}