Wednesday, December 16, 2015

int GetSizeOfGreatestRectangleOf1or0( int [,] binaries, int rows, int cols)
{
   var rectangles = new SortedList<int, int>();
   for (int k = 0; k < rows*cols; k++)
   {
         int row = k / cols;
         int col = k % cols;
         bool inRectangle = false;

         for (int l = 0; l < rectangles.Count; l++)
         {
             if (rectangles.GetKey(l) <= k && rectangles.GetByIndex(l) > k){
             {
                int startrow = rectangles.GetKey(l) / cols;
                int startcol = rectangles.GetKey(l) % cols;
                Debug.Assert(binaries[startrow, starcol] == binaries[row, col]);
                // already part of rectangle
                inRectangle = true;
                break;
             }
         }

         /*if (inRectangle)
         {
             continue;
         }else */ {
            // add rectangle if exists
            // starting at this point as top left
// we walk the rectangle based on increasing diagonal or side bottom or right and making sure all newly encountered elements within the new bounds are of similar value.
       
         }
   }

   // with all rectangles return max size
   int size = 0;
   for (int l = 0; l < rectangles.Count; l++)
   {
     int startrow = rectangles.GetKey(l) / cols;
     int startcol = rectangles.GetKey(l) % cols;
     int endrow = rectangles.GetByIndex(l) / cols;
     int endcol = rectangles.GetByIndex(l) % cols;
     Debug.Assert(endcol > startcol && endrow > startrow);
     int cursize = (endcol - startcol + 1) * (endrow - startrow + 1);
     if (cursize > size)
     {
         size = cursize;
     }
   }
   return size;
}

No comments:

Post a Comment