Wednesday, June 12, 2013

Given a two dimensional matrix of booleans, write a function that returns the number of "true regions". (C#)

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

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: