Microsoft Interview Question
InternsCountry: 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