using System.Collections.Generic;

using System;

using System.Linq;

​

public class Program {

    private const int capacity = 625;

​

    public static void Main() {

        int[] range = new int[capacity]; //Enumerable.Range(0, 100).ToArray();

        int width = (int)Math.Sqrt(capacity),

            height = (int)Math.Sqrt(capacity);

        range = DrawCircle(range, 0, 0, width, height, 5);

        Console.WriteLine();

        Console.WriteLine();

​

        Print(range, (int)Math.Sqrt(capacity));

        Console.WriteLine();

        Console.WriteLine();

        int i = 0;

        for(int j = 0; j < capacity; ++j) 

        {

            int num = range[j];

            if(num == 1) 

            {

                int x = j % width, 

                    y = j / width;

                FloodFillHash(range, x, y, width, height, 1, 2, out i);

            }

        }

        Print(range, (int)Math.Sqrt(capacity));

        Console.WriteLine();

        Console.WriteLine();

        Console.WriteLine("Iterations: {0}", i);

    }

    private static int[] DrawCircle(int[] source, int x, int y, int width, int height, int r, bool inCenter = true) 

    {

        int i = 0;

        int rSquared = r * r;

        if(inCenter) {

            x += width / 2;

            y += height / 2;

        }

        for (int u = 0; u < width; ++u) {

            for (int v = 0; v < height; ++v) {

                if ((x-u)*(x-u) + (y-v)*(y-v) < rSquared) {

                    source[Pn(u, v, width)] = 1;

                    ++i;

                }

            }

        }

        Console.WriteLine("Iterations: {0}", i);

        return source;

    }

​

    private static void Print < T > (T[] objs, int splitEvery = 10) {

        int i = 1;

        foreach(T item in objs) {

            Console.Write(item);

            if (i % splitEvery == 0) 

                Console.WriteLine(); ++i;

        }

    }

​

    public static int P(int x, int y, int w, int h) {

        // (h - y - 1)

        // y

        return x + ((h - y - 1) * w);

    }

​

    public static int Pn(int x, int y, int w) {

        return x + (y * w);

    }

​

    public static void FloodFill(int[] source, int x, int y, int width, int height, int targetColor, int replacementColor, out int i) {

        i = 0;

        Stack < int > pixels = new Stack < int > ();

​

        targetColor = source[P(x, y, width, height)];

        pixels.Push(Pn(x, y, width));

​

        while (pixels.Count > 0) {

            int _i = pixels.Pop(),

            _x = _i % width,

            _y = _i / width;

​

            //if (a.x >= width || a.x < 0 || a.y >= height || a.y < 0)

            //    return;

​

            if (source[P(_x, _y, width, height)] == targetColor) {

                source[P(_x, _y, width, height)] = replacementColor;

​

                if (_x > 0) pixels.Push(Pn(_x - 1, _y, width));

​

                if (_x < width - 1) pixels.Push(Pn(_x + 1, _y, width));

​

                if (_y > 0) pixels.Push(Pn(_x, _y - 1, width));

​

                if (_y < height - 1) pixels.Push(Pn(_x, _y + 1, width));

            }

​

            ++i;

        }

    }

    public static void FloodFillHash(int[] source, int x, int y, int width, int height, int targetColor, int replacementColor, out int i) {

        i = 0;

        // HashSet < int > sector = new HashSet < int > ();

        // HashSet < int > checkd = new HashSet < int > ();

        HashSet < int > queue = new HashSet < int > ();

        HashSet < int > processed = new HashSet < int > ();

​

        targetColor = source[P(x, y, width, height)];

        if(targetColor == replacementColor)

            return;

        queue.Add(Pn(x, y, width));

​

        while (queue.Count > 0) 

        {

            int _i = queue.First(),

            _x = _i % width,

            _y = _i / width;

            // sector.Add(_i);

            // checkd.Add(_i);

            ++i;

            queue.Add(_i); // Pn(x, y, width)

            if(!processed.Add(_i))

            {

                queue.Remove(_i);

                continue;

            }

            for (int offsetX = -1; offsetX < 2; offsetX++)

                for (int offsetY = -1; offsetY < 2; offsetY++)

                {

                    // do not check origin or diagonal neighbours

                    if (offsetX == 0 && offsetY == 0 || offsetX == offsetY || offsetX == -offsetY || -offsetX == offsetY) continue;

​

                    int target = Pn(_x + offsetX, _y + offsetY, width);

​

                    int _tx = target % width,

                        _ty = target / width;

​

                    // skip out of bounds point

                    if (_tx < 0 || _ty < 0 || _tx >= width || _ty >= height) continue;

                    if(!processed.Add(target))

                        continue;

                    source[target] = replacementColor;

​

                    ++i;

                }

        }

    }

}