## Microsoft Interview Question

Interns**Country:**United States

//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()

// }

//}

```
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);
}
}
```

- srterpe January 12, 2017