Problem Statement for grafixMask
using System;
using System.Collections.Generic;
namespace TopCoder.GraphPractice
{
class grafixMask
{
public int[] sortedAreas(String[] rectangles)
{
bool[,] visited = GetBlockedPixels(rectangles);
List<int> areas = new List<int>();
for (int row = 0; row < 400; row++)
{
for (int col = 0; col < 600; col++)
{
if (!visited[row, col])
{
areas.Add(GetConnectedArea(row, col, ref visited));
}
}
}
areas.Sort();
return areas.ToArray();
}
private bool[,] GetBlockedPixels(String[] rectangles)
{
bool[,] blocked = new bool[400, 600];
foreach (String rectangle in rectangles)
{
String[] coordinates = rectangle.Split();
int topLeftRow = Int32.Parse(coordinates[0]);
int topLeftCol = Int32.Parse(coordinates[1]);
int bottomRightRow = Int32.Parse(coordinates[2]);
int bottomRightCol = Int32.Parse(coordinates[3]);
for (int row = topLeftRow; row <= bottomRightRow; row++)
{
for (int col = topLeftCol; col <= bottomRightCol; col++)
{
blocked[row, col] = true;
}
}
}
return blocked;
}
// Depth first search.
private int GetConnectedArea(int row, int col, ref bool[,] visited)
{
int area = 0;
Stack<Vertex> stack = new Stack<Vertex>();
stack.Push(new Vertex(row, col));
while (stack.Count > 0)
{
Vertex top = stack.Pop();
if (top.Row < 0 || top.Row >= 400)
{
continue;
}
if (top.Col < 0 || top.Col >= 600)
{
continue;
}
if (visited[top.Row, top.Col])
{
continue;
}
visited[top.Row, top.Col] = true;
area++;
stack.Push(new Vertex(top.Row + 1, top.Col));
stack.Push(new Vertex(top.Row - 1, top.Col));
stack.Push(new Vertex(top.Row, top.Col + 1));
stack.Push(new Vertex(top.Row, top.Col - 1));
}
return area;
}
private class Vertex
{
public int Row { get; set; }
public int Col { get; set; }
public Vertex(int row, int col)
{
Row = row;
Col = col;
}
}
}
}
沒有留言:
張貼留言