COUNT MAX NUMBER OF CONNECTED 1s IN A MATRIX
namespace CountMaxNoOfConnected1s
{
//you have a matrix of N x N filled with 1 or 0. you can move
//only 1 step either right or 1 step down. you need to count
//maximum number of "connected 1" in given matrix. for example
//0 0 1 1
//1 1 1 0
//1 0 1 0
//0 1 0 1
//[Start from top left] maximum no. of connected 1s is 4
//[1,0][1,1][1,2][2,2]
class Program
{
static int MaxNoOfConnected1s(int[,] Mat)
{
int[,] ComputeMat = new int[Mat.GetLength(0), Mat.GetLength(1)];
int Max1s = 0;
for (int i = 0; i < Mat.GetLength(0); i++)
{
for (int j = 0; j < Mat.GetLength(1); j++)
{
if (i > 0 || j > 0)
{
if (i > 0 && j > 0)
{
if (Mat[i - 1, j] == 1 || Mat[i, j - 1] == 1)
{
ComputeMat[i, j] = Math.Max(ComputeMat[i - 1, j], ComputeMat[i, j - 1]) + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}
else if (i > 0)
{
if (Mat[i - 1, j] == 1)
{
ComputeMat[i, j] = ComputeMat[i - 1, j] + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}
else if (j > 0)
{
if (Mat[i, j-1] == 1)
{
ComputeMat[i, j] = ComputeMat[i, j-1] + Mat[i, j];
}
else ComputeMat[i, j] = Mat[i, j];
}
if (ComputeMat[i, j] > Max1s) Max1s = ComputeMat[i, j];
}
}
}
return Max1s;
}
static void Main(string[] args)
{
int[,] Mat = {
{0,0,1,1},
{1,1,1,0},
{1,0,1,0},
{0,1,1,1}
};
Console.WriteLine(MaxNoOfConnected1s(Mat));
}
}
}
No comments:
Post a Comment