import numpy as np
import random
import sys
sys.setrecursionlimit(30000)
class ConnectedComponent():

    def boundOut(self,heigth,width,y,x):
        if y<0 or x<0 or y>=heigth or x>=width:
            return True
        return False

    def findChildern(self,A,R,y,x,color):
        heigth,width=A.shape
        if(not self.boundOut(heigth,width,y,x+1) and A[y][x+1]!=0):
            R[y][x+1]=color
            A[y][x+1]=0
            self.findChildern(A,R,y,x+1,color)
        elif(not self.boundOut(heigth,width,y,x-1) and A[y][x-1]!=0):
            R[y][x-1]=color
            A[y][x-1]=0
            self.findChildern(A,R,y,x-1,color)
        elif(not self.boundOut(heigth,width,y+1,x) and A[y+1][x]!=0):
            R[y+1][x]=color
            A[y+1][x]=0
            self.findChildern(A,R,y+1,x,color)
        elif(not self.boundOut(heigth,width,y-1,x) and A[y-1][x]!=0):
            R[y-1][x]=color
            A[y-1][x]=0
            self.findChildern(A,R,y-1,x,color)
        elif(not self.boundOut(heigth,width,y+1,x+1) and A[y+1][x+1]!=0):
            R[y+1][x+1]=color
            A[y+1][x+1]=0
            self.findChildern(A,R,y+1,x+1,color)
        elif(not self.boundOut(heigth,width,y-1,x-1) and A[y-1][x-1]!=0):
            R[y-1][x-1]=color
            A[y-1][x-1]=0
            self.findChildern(A,R,y-1,x-1,color)
        elif(not self.boundOut(heigth,width,y+1,x-1) and A[y+1][x-1]!=0):
            R[y+1][x-1]=color
            A[y+1][x-1]=0
            self.findChildern(A,R,y+1,x-1,color)
        elif(not self.boundOut(heigth,width,y-1,x+1) and A[y-1][x+1]!=0):
            R[y-1][x+1]=color
            A[y-1][x+1]=0
            self.findChildern(A,R,y-1,x+1,color)

    def bruteforce(self,matrix):
        result=np.zeros((matrix.shape[0],matrix.shape[1],3))

        for y in xrange(matrix.shape[0]):
            for x in xrange(matrix.shape[1]):
                if (matrix[y][x]!=0):
                    matrix[y][x]=0
                    color=np.array([int(random.random()*255),int(random.random()*255),int(random.random()*255)])
                    result[y][x]=color
                    self.findChildern(matrix,result,y,x,color)
        return result