CareerCup

/**
 * Given an `N`x`N` Boolean matrix, find how many true
 * regions there are in the matrix.
 */

// Define a `true region` as any contiguous set of 
// true elements such that the true elements are 
// touching either horizontally, vertically, or
// diagonally.


// For each `i`,`j` element in the matrix, if it is
// `true` mark it as "unvisited" and put it in the
// search set.

// Set `r` to be 0, the number of unique regions.

// While there are elements in the search set,
// take an element from the search set, if it
// is "visited", discard it, if it is "unvisited"
// mark it as "visited", and put it in the
// working set and increment `r`.

// While there are elements in the working set,
// take the next element from the working set,
// if it has any `true` neighbors among it's
// 8 possible neighbors, mark those neighbors 
// as "visited" and add them to the working
// set.

// Return `r` the number of contiguous true regions of
// the `N`x`N` matrix.

//regions =0
// visited_set = new hashset()
//for each t[i,j]
//{
// if t[i,j] in visited_set or is false continue;
//
// regions ++
// Stack region_cells = new Stack();
// current = t[i,j]
// -- let's visit all true cells in this region and mark then so we will skip them later
// while (current != null)
// {
// for each neighbor of current
// {
// if (neighbor is true and not in visited_set)
// {
// stack.push(neighbor)
// visited_set.add(neighbor)
// }
// }
// current = stack.pop()
// }
//}

can be done using union-find data structure with one pass on the matrix

can be done using union-find data structure with one pass on the matrix.
time: O(log*(NxN))

public static int TrueRegionCount(Boolean[][] regions)
{
    int newRegions = 0;
    for (int i = 0; i < regions.Length; i++)
    {
        for (int j = 0; j < regions[i].Length; j++)
        {
            if (isNewRegion(regions, i, j))
            {
                newRegions++;
            }
        }
    }
    return newRegions;
}

private static Boolean isNewRegion(Boolean[][] regions, int i, int j)
{
    return (regions[i][j] &&
        !(((i > 0) &&
            ((j > 0) && (regions[i - 1][j - 1]) ||
            regions[i - 1][j] ||
            ((j < regions.Length - 1) && regions[i - 1][j + 1]))
        ) ||
        ((j > 1) && regions[i][j - 1])
        //Following are not visited yet
        //||((j < regions.Length - 1) && regions[i][j+1]) ||
        //((i < regions.Length -1) &&
        //((j > 1) && regions[i+1][j-1] ||
        //regions[i+1][j] ||
        //regions[i+1][j+1] )
        ));
}

static void MarkedasTrue(int[,] myMatrix)
        {
            int[,] ValueChanged = new int[3,3];
          
            for (int i = 0; i < myMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < myMatrix.GetLength(1); j++)
                {
                    if (myMatrix[i,j]==1)
                    {
                        for (int k = 0; k < myMatrix.GetLength(1); k++)
                        {
                            ValueChanged[i, k] = 1;
                        }
                        for (int l = 0; l < myMatrix.GetLength(0); l++)
                        {
                            ValueChanged[l, j] = 1;
                        }
                    }
                }
            }

            myMatrix = ValueChanged;

            PrintMatrix(myMatrix);
        }

int GetTrueRegions(bool[,] m)
{
boo[,] visited = new bool[m.GetLength(0),m.GetLength(1)];
int counts = 0;
for(int i=0;i<m.GetLength(0);i++)
{
for(int j=0;j<m.GetLength(1);j++)
{
if(m[i,j] && !v[i,j])
{
counts = 0;
VisitConnected(m, visited, i, j);
}
}

}

}


void VisitConnected(bool[,] m, bool[,] visited, int i, int j)
{
if(i < m.GetLength(0) && j < m.GetLength(1) && m[i,j])
{
visited[i,j]=true;
VisitConnected(m, visited, i+1, j);
VisitConnected(m, visited, i, j+1);
VisitConnected(m, visited, i+1, j+1);
}
}

public static int GetTrueRegions(bool[,] m)
        {
            bool[,] visited = new bool[m.GetLength(0), m.GetLength(1)];
            int counts = 0;
            for (int i = 0; i < m.GetLength(0); i++)
            {
                for (int j = 0; j < m.GetLength(1); j++)
                {
                    if (m[i, j] && !visited[i, j])
                    {
                        counts++;
                        VisitConnected(m, visited, i, j);
                    }
                }

            }
            return counts;
        }


        static void VisitConnected(bool[,] m, bool[,] visited, int i, int j)
        {
            if (i < m.GetLength(0) && j < m.GetLength(1) && m[i, j])
            {
                visited[i, j] = true;
                VisitConnected(m, visited, i + 1, j);
                VisitConnected(m, visited, i, j + 1);
                VisitConnected(m, visited, i + 1, j + 1);
            }
        }

let result = 0;
For each element:
if element==false: continue;
else element == true:
if any true elements are 'touching' this current element, set current elem to false
else result++

analysis: O(n) as there are in the worst case 8 neighbors to check per item if it is true