2013年4月21日 星期日

[C#] Depth First Search


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;
            }
        }
    }
}

沒有留言:

張貼留言