Number of closed rectangles in a matrix

Given a matrix containing only 1 and 0, find the number of closed rectangles. A closed rectangle is represented by at least one 0 surrounded by eight 1′s. There is no overlap of closed rectangles.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] inputMatrix = {
                                     {1, 1, 1, 1, 1, 1, 1},
                                     {1, 0, 0, 0, 1, 0, 1},
                                     {1, 0, 1, 1, 1, 1, 1},
                                     {1, 0, 1, 0, 1, 0, 1},
                                     {1, 1, 1, 1, 1, 0, 1}, 
                                     {1, 0, 1, 0, 0, 0, 1},
                                     {1, 1, 1, 1, 1, 1, 1}
                                 };
            //Initial window size
            int rowSize = 3, colSize = 3;
            int count = 0;
            for (int windowHeight = rowSize; windowHeight <= inputMatrix.GetLength(0); windowHeight++)
            {
                for (int windowLength = colSize; windowLength <= inputMatrix.GetLength(1); windowLength++)
                {
                    //Starting position
                    for (int startRow = 0; startRow + windowHeight <= inputMatrix.GetLength(0); startRow++)
                    {
                        for (int startCol = 0; startCol + windowLength <= inputMatrix.GetLength(1); startCol++)
                        {
                            if (checkClosedPattern(GetSubMatrix(startRow, startCol, windowHeight, windowLength, inputMatrix)))
                            {
                                count++;
                            }
                        }
                    }
                }
            }
            Console.WriteLine("Number of closed patterns = " + count);
        }

        public static int[,] GetSubMatrix(int startRow, int startCol, int rowLen, int colLen, int[,] inputMatrix)
        {
            int[,] subMatrix = new int[rowLen, colLen];
            for (int i = startRow; i < startRow + rowLen; i++)
            {
                for (int j = startCol; j < startCol + colLen; j++)
                {
                    subMatrix[i - startRow, j - startCol] = inputMatrix[i, j];
                }
            }
            return subMatrix;
        }

        public static bool checkClosedPattern(int[,] subMatrix)
        {
            //Check for boundary 1's and inner 0's
            for (int i = 0; i < subMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < subMatrix.GetLength(1); j++)
                {
                    //Top row
                    if (i == 0 && subMatrix[i, j] != 1)
                    {
                        return false;
                    }
                    //Bottom row
                    if (i == subMatrix.GetLength(0) - 1 && subMatrix[i, j] != 1)
                    {
                        return false;
                    }
                    //First Column
                    if (j == 0 && subMatrix[i, j] != 1)
                    {
                        return false;
                    }
                    //Last Column
                    if (j == subMatrix.GetLength(1) - 1 && subMatrix[i, j] != 1)
                    {
                        return false;
                    }
                    //Inner elements
                    if (i != 0 && i != subMatrix.GetLength(0) - 1 && j != 0 && j != subMatrix.GetLength(1) - 1 && subMatrix[i, j] != 0)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}

Output
=======
Number of closed patterns = 3
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s