using System.Collections.Generic;
public static void Main()
GridWithSingleRectangle();
Console.WriteLine("------------");
GridWithMultipleRectangles();
private static void GridWithSingleRectangle()
var grid = new Grid(10, 10);
grid.FillRectangle(new Coord(1, 5), new Coord(3, 8));
var actual = GetSingleRectangle(grid);
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)
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);
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);
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));
var actual = GetMultipleRectangle(grid);
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)
public Coord(int x, int 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);
private readonly int[,] _grid;
get { return this._grid.GetLength(1); }
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++)
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++)
sb.AppendLine(string.Join(", ", row));