using System;

using System.Collections.Generic;

using System.Text;

​

public class Program

{

    public static void Main()

    {

        GridWithSingleRectangle();

        Console.WriteLine("------------");

        GridWithMultipleRectangles();

    }

    // Problem one, find a solid rectangle of 1s in a grid of 0s.   

    private static void GridWithSingleRectangle()

    {

        var grid = new Grid(10, 10);

        grid.FillRectangle(new Coord(1, 5), new Coord(3, 8));

        Console.WriteLine(grid);

        var actual = GetSingleRectangle(grid);

        if (actual != null)

        {

            Console.WriteLine(String.Format("Grid found. Coords: {0}, {1}", actual.Item1, actual.Item2));

        }

        else Console.WriteLine("no grid found");

    }

    private static Tuple<Coord, Coord> GetSingleRectangle(Grid grid)

    {

        int minX = grid.Width;

        int minY = grid.Height;

        int maxX = 0;

        int maxY = 0;

        int count = 0;

        for (int x = 0; x < grid.Width; x++)

        {

            for (int y = 0; y < grid.Height; y++)

            {

                if (grid.GetValue(new Coord(x, y)) == 1)

                {

                    minY = Math.Min(minY, y);

                    minX = Math.Min(minX, x);

                    maxX = Math.Max(maxX, x);

                    maxY = Math.Max(maxY, y);

                    count++;

                }

            }

        }

        var topLeft = new Coord(minX, minY);

        var bottomRight = new Coord(maxX, maxY);

        var expectedArea = (bottomRight.X - topLeft.X + 1) * (bottomRight.Y - topLeft.Y + 1);

        if (count == expectedArea)

        {

            return new Tuple<Coord, Coord>(topLeft, bottomRight);

        }

        return null;

    }

    // Problem two, find multiple solid rectangles of 1s in a grid of 0s

    private static void GridWithMultipleRectangles()

    {

        var grid = new Grid(10, 10);

        grid.FillRectangle(new Coord(1, 5), new Coord(3, 8));

        grid.FillRectangle(new Coord(1, 1), new Coord(4, 3));

        grid.FillRectangle(new Coord(6, 1), new Coord(8, 3));

        Console.WriteLine(grid);

        var actual = GetMultipleRectangle(grid);

        if (actual != null)

        {

            foreach (var tuple in actual)

            {

                Console.WriteLine(String.Format("Grid found. Coords: {0}, {1}", tuple.Item1, tuple.Item2));

            }

        }

        else Console.WriteLine("no grids found");

    }

    private static List<Tuple<Coord, Coord>> GetMultipleRectangle(Grid grid)

    {

        return null;

    }

}

​

public class Coord

{

    public Coord(int x, int y)

    {

        this.X = x;

        this.Y = y;

    }

    public int X { get; private set; }

    public int Y { get; private set; }

    public override string ToString()

    {

        return string.Format("(x:{0}, y:{1})", X, Y);

    }

}

​

public class Grid

{

    private readonly int[,] _grid;

    public int Width

    {

        get { return this._grid.GetLength(1); }

    }

    public int Height

    {

        get { return this._grid.GetLength(0); }

    }

    public Grid(int height, int width)

    {

        this._grid = new int[height, width];

    }

    public void SetValue(Coord coord, int val)

    {

        this._grid[coord.Y, coord.X] = val;

    }

    public int GetValue(Coord coord)

    {

        return this._grid[coord.Y, coord.X];

    }

    public void FillRectangle(Coord topLeft, Coord bottomRight)

    {

        Console.WriteLine(string.Format("Grid between: {0} and {1}", topLeft, bottomRight));

        for (var x = topLeft.X; x <= bottomRight.X; x++)

        {

            for (var y = topLeft.Y; y <= bottomRight.Y; y++)

            {

                _grid[y, x] = 1;

            }

        }

    }

    public override string ToString()

    {

        var sb = new StringBuilder();

        for (var i = 0; i < _grid.GetLength(0); i++)

        {

            var row = new List<int>();

            for (var j = 0; j < _grid.GetLength(1); j++)

            {

                row.Add(_grid[i, j]);

            }

            sb.AppendLine(string.Join(", ", row));

        }

        return sb.ToString();

    }

}