Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Diagnostics;
- using System.Linq;
- namespace FloodFill
- {
- internal class Program
- {
- private const int MAP_SIZE = 4096; // only powers of two are supported
- private static void Main()
- {
- var map = new byte[MAP_SIZE * MAP_SIZE];
- var stopwatch = Stopwatch.StartNew();
- {
- FloodFill(map, startX: 123, startY: 123, fromValue: 0, toValue: 1);
- }
- stopwatch.Stop();
- Console.WriteLine(stopwatch.ElapsedMilliseconds);
- // Test results
- if (map.Any(item => item == 0))
- {
- Console.WriteLine("Error");
- }
- else
- {
- Console.WriteLine("Ok");
- }
- Console.ReadLine();
- }
- private static unsafe void FloodFill(byte[] map, int startX, int startY, byte fromValue, byte toValue)
- {
- int shift = (int)Math.Round(Math.Log(map.Length, 4)); // if the array's length is (2^x * 2^x), then shift = x
- int startIndex = startX + (startY << shift);
- if (map[startIndex] != fromValue)
- {
- return;
- }
- // initialize flood fill
- int size = 1 << shift;
- int sizeMinusOne = size - 1;
- int xMask = size - 1;
- int minIndexForVerticalCheck = size;
- int maxIndexForVerticalCheck = map.Length - size - 1;
- // initialize queue
- int capacity = size * 2;
- int mask = capacity - 1;
- uint tail = 0;
- uint head = 0;
- var queue = new int[capacity];
- fixed (byte* m = map)
- fixed (int* q = queue)
- {
- *(m + startIndex) = toValue;
- *(q + (tail++ & mask)) = startIndex;
- while (tail - head > 0)
- {
- int index = q[head++ & mask];
- int x = index & xMask;
- byte* p = m + index;
- if (x > 0 && *(p - 1) == fromValue)
- {
- *(p - 1) = toValue;
- *(q + (tail++ & mask)) = index - 1;
- }
- if (x < sizeMinusOne && *(p + 1) == fromValue)
- {
- *(p + 1) = toValue;
- *(q + (tail++ & mask)) = index + 1;
- }
- if (index >= minIndexForVerticalCheck && *(p - size) == fromValue)
- {
- *(p - size) = toValue;
- *(q + (tail++ & mask)) = index - size;
- }
- if (index <= maxIndexForVerticalCheck && *(p + size) == fromValue)
- {
- *(p + size) = toValue;
- *(q + (tail++ & mask)) = index + size;
- }
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement