Maximum resultant height of a matrix

Given a matrix containing only 0 and 1, find the maximum resultant height of the matrix as described below:
The colored cells are represented by 1 and white cells are represented by 0.

Four contiguous colored cells at a level form a colored cell at the next higher level as shown below:

An example configuration of cells in a matrix is shown below:

The expected output for the above example is 3.

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[,] inputMatrix = new string[,]
            {
                {"1", "1", "1", "1", "0", "0", "0", "0"},    
                {"1", "0", "1", "1", "0", "0", "0", "0"},
                {"1", "1", "1", "1", "0", "0", "0", "0"},
                {"1", "1", "1", "1", "1", "0", "0", "0"},
                {"0", "0", "0", "1", "1", "1", "1", "1"},    
                {"0", "0", "0", "0", "1", "1", "1", "1"},
                {"0", "0", "0", "0", "1", "1", "0", "1"},
                {"0", "0", "0", "0", "1", "1", "1", "1"}
            };
            int currentLevel = 1;
            //Window Dimension
            for (int k = 2; k <= Math.Min(inputMatrix.GetLength(0), inputMatrix.GetLength(1)); k++)
            {
                //Starting Point
                for (int i = 0; (i + k) <= inputMatrix.GetLength(0); i++)
                {
                    for (int j = 0; (j + k) <= inputMatrix.GetLength(1); j++)
                    {
                        //Check the sub matrix element of dimension (k, k)
                        if (CheckMatrix(inputMatrix, k, i, j, k - 1))
                        {
                            currentLevel = k;
                            //Fill the matrix with 0 + (k - 1)
                            FillMatrix(inputMatrix, k, i, j, "0" + (k - 1).ToString());
                        }
                    }
                }
                //Replace 0 + (k - 1) in the matrix with with k
                ReplaceMatrix(inputMatrix, "0" + (k - 1).ToString(), k.ToString());
            }
            Console.WriteLine("Max Level = " + currentLevel);
        }
        public static bool CheckMatrix(string[,] inputMatrix, int k, int i, int j, int num)
        {
            for (int p = i; p < (i + k); p++)
            {
                for (int q = j; q < (j + k); q++)
                {
                    if (int.Parse(inputMatrix[p, q]) != num)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
        public static void FillMatrix(string[,] inputMatrix, int k, int i, int j, string str)
        {
            for (int p = i; p < (i + k); p++)
            {
                for (int q = j; q < (j + k); q++)
                {
                    inputMatrix[p, q] = str;
                }
            }
        }
        public static void ReplaceMatrix(string[,] inputMatrix, string oldValue, string newValue)
        {
            for (int i = 0; i < inputMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < inputMatrix.GetLength(1); j++)
                {
                    if (inputMatrix[i, j] == oldValue)
                    {
                        inputMatrix[i, j] = newValue;
                    }
                }
            }
        }
    }
}

Output
=======
Max Level = 2
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