Given a two dimensional matrix of booleans, there is a function that returns the number of "true regions". A region is a group of True values aligned vertically or horizontally.
T T <= 3 region
T F
T F <= 2 regions
F T
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Configuration;
namespace Excercises
{
class Program
{
static void Main(string[] args)
{
bool[,] region1 = new bool[2,2]{ { true, false }, { true, true }};
int numOfRegions = returnRegion(region1);
Console.WriteLine(numOfRegions.ToString());
Console.ReadKey();
}
public static int returnRegion(bool[,] region1)
{
int count =0;
int rowLen = region1.GetLength(0);
int columnLen = region1.GetLength(1);
for (int row = 0; row < rowLen ; row++)
{
for (int column = 0; column < columnLen; column++)
{
if (region1[row, column] == true)
{
count++;
}
}
}
return count;
}
}
}
Complexity is O(2N)
T T <= 3 region
T F
T F <= 2 regions
F T
Question
Write the code to solve this problem. What are the time and space complexities?using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Configuration;
namespace Excercises
{
class Program
{
static void Main(string[] args)
{
bool[,] region1 = new bool[2,2]{ { true, false }, { true, true }};
int numOfRegions = returnRegion(region1);
Console.WriteLine(numOfRegions.ToString());
Console.ReadKey();
}
public static int returnRegion(bool[,] region1)
{
int count =0;
int rowLen = region1.GetLength(0);
int columnLen = region1.GetLength(1);
for (int row = 0; row < rowLen ; row++)
{
for (int column = 0; column < columnLen; column++)
{
if (region1[row, column] == true)
{
count++;
}
}
}
return count;
}
}
}
Complexity is O(2N)
No comments:
Post a Comment