Yandex Algorithms 2017 Marathon

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

class Solution
{
    static int width;
    static int height;
    static int k;
    static Point[] life;
    static Point[] magic;
    static Random random = new Random();
    static bool[,] fountain;

    static int[,] dirRandom = new int[,] {
        {0,1,2,3},
        {0,1,3,2},
        {0,2,1,3},
        {0,2,3,1},
        {0,3,1,2},
        {0,3,2,1},
        {1,0,2,3},
        {1,0,3,2},
        {1,2,0,3},
        {1,2,3,0},
        {1,3,0,2},
        {1,3,2,0},
        {2,1,0,3},
        {2,1,3,0},
        {2,0,1,3},
        {2,0,3,1},
        {2,3,1,0},
        {2,3,0,1},
        {3,1,2,0},
        {3,1,0,2},
        {3,2,1,0},
        {3,2,0,1},
        {3,0,1,2},
        {3,0,2,1},
    };

    static void Main(string[] args)
    {
        int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
        height = nums [0];
        width = nums [1];
        k = nums [2];
        life = new Point[k];
        fountain = new bool[width, height];
        for (int i = 0; i < k; i++) {
            nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
            life [i] = new Point (nums [1], nums [0]);
            fountain [nums [1], nums [0]] = true;
        }
        magic = new Point[k];
        for (int i = 0; i < k; i++) {
            nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
            magic [i] = new Point (nums [1], nums [0]);
            fountain [nums [1], nums [0]] = true;
        }

        double bestScore = -1;
        int counter = 0;
        int[,] solution = new int[width, height];
        Stopwatch sw = Stopwatch.StartNew ();


        while (sw.ElapsedMilliseconds < 1000 || solution == null) {
            int[,] grid = GenerateGrid ();
            if (grid == null)
                continue;
            counter++;
            double score = ScoreGrid (grid);
            if (score > bestScore) {
                bestScore = score;
                solution = grid;
            }
        }
        Console.Error.WriteLine ("sims: " + counter);
        Console.Error.WriteLine ("score: " + (int)(bestScore * 160000 / k));

        counter = 0;
        while (sw.ElapsedMilliseconds < 1950) {
            int[,] grid = ExpandGrid (solution);
            if (grid == null)
                continue;
            counter++;
            double score = ScoreGrid(grid);
            if (score > bestScore) {
                solution = grid;
                bestScore = score;
            }
        }

        Console.Error.WriteLine ("expand sims: " + counter);
        Console.Error.WriteLine ("expand score: " + (int)(bestScore * 160000 / k));
        Print (solution);
    }

    static bool ExpandEdge(int[,] grid) {
        int x, y, dir, value;
        int x_, y_;
        while (true) {
            x = random.Next (width);
            y = random.Next (height);
            dir = random.Next (4);
            value = grid [x, y];
            x_ = x + offset [dir, 0];
            y_ = y + offset [dir, 1];
            if (x_ >= 0 && x_ < width && y_ >= 0 && y_ < height && grid [x_, y_] != value && !fountain [x_, y_])
                break;
        }

        List<Point> change = new List<Point> { new Point (x_, y_) };
        foreach (int newDir in new int[] {(dir+1)%4, (dir+3)%4}) {
            for (int dist = 1;; dist++) {
                int myX = x + dist * offset [newDir, 0];
                int myY = y + dist * offset [newDir, 1];
                int otherX = x + dist * offset [newDir, 0] + offset [dir, 0];
                int otherY = y + dist * offset [newDir, 1] + offset [dir, 1];
                if (myX < 0 || myX >= width || myY < 0 || myY >= height || grid [myX, myY] != value || fountain [otherX, otherY])
                    break;
                change.Add (new Point (otherX, otherY));
            }
        }
        foreach (Point p in change) {
            grid [p.X, p.Y] = value;
        }
        return true;
    }

    static int[,] ExpandGrid(int[,] oldGrid) {
        int[,] grid = (int[,])oldGrid.Clone ();
        do {
            if (!ExpandEdge (grid)) return null;
        } while (random.NextDouble () < 0.25);
        if (!CheckConnected ((int[,])grid.Clone ()))
            return null;

        return grid;
    }

    static Point[] stack = new Point[50 * 50];
    static int stackIndex = 0;
    static bool CheckConnected(int[,] grid) {
        int components = 0;
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                if (grid [x, y] == 0)
                    continue;
                components++;
                stack [stackIndex++] = new Point (x, y);
                while (stackIndex > 0) {
                    Point p = stack [--stackIndex];
                    int value = grid [p.X, p.Y];
                    if (value == 0)
                        continue;
                    grid [p.X, p.Y] = 0;
                    if (p.X > 0 && grid [p.X - 1, p.Y] == value)
                        stack [stackIndex++] = new Point (p.X - 1, p.Y);
                    if (p.X + 1 < width && grid [p.X + 1, p.Y] == value)
                        stack [stackIndex++] = new Point (p.X + 1, p.Y);
                    if (p.Y > 0 && grid [p.X, p.Y - 1] == value)
                        stack [stackIndex++] = new Point (p.X, p.Y - 1);
                    if (p.Y + 1 < height && grid [p.X, p.Y + 1] == value)
                        stack [stackIndex++] = new Point (p.X, p.Y + 1);
                }
            }
        }
        return components == k;
    }

    static void Print(int[,] grid) {
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                Console.Write ((char)('a' + grid [x, y] - 1));
            }
            Console.WriteLine ();
        }
    }

    static int[,] GenerateGrid() {
        int[,] result = new int[width,height];
        MapPairs (result);

        //sort mappings by manhattan distance
        int[] indices = Enumerable.Range(0,k).ToArray();
        int[] dist = new int[k];
        for (int i = 0; i < k; i++) {
            dist [i] = Math.Abs (life [i].X - magic [i].X) + Math.Abs (life [i].Y - magic [i].Y);
        }
        Array.Sort (dist, indices);

        foreach(int i in indices) {
            if (!ConnectPair (result, life [i], magic [i], i + 1))
                return null;
        }

        FillGaps (result);
        return result;
    }

    static void MapPairs(int[,] grid) {
        int index1 = random.Next (k);
        int index2 = random.Next (k);
        Point tmp = magic [index1];
        magic [index1] = magic [index2];
        magic [index2] = tmp;

        for (int index = 0; index < k; index++) {
            double[] prob = new double[k - index];
            int probIndex = 0;
            for (int partner = index; partner < k; partner++) {
                int dx = Math.Abs (magic [index].X - life [partner].X);
                int dy = Math.Abs (magic [index].Y - life [partner].Y);
                prob [probIndex++] = 1.0 / (dx * dx + dy * dy);
            }
            for (int i = 1; i < k-index; i++) {
                prob [i] += prob [i - 1];
            }
            double randVal = prob [k - index - 1] * random.NextDouble ();
            int takeIndex = 0;
            while (prob [takeIndex] < randVal)
                takeIndex++;
            tmp = life [index];
            life [index] = life [index + takeIndex];
            life [index + takeIndex] = tmp;
            grid [life [index].X, life [index].Y] = index + 1;
            grid [magic [index].X, magic [index].Y] = index + 1;
        }
    }

    static Point[] queue = new Point[50 * 50];
    static bool ConnectPair(int[,] grid, Point p1, Point p2, int value) {
        int[,] dist = new int[width, height];
        dist [p1.X, p1.Y] = 1;
        int queueFirst = 0;
        int queueLast = 0;
        queue [queueLast++] = p1;
        while (queueFirst < queueLast && dist [p2.X, p2.Y] == 0) {
            Point p = queue [queueFirst++];
            for (int dir = 0; dir < 4; dir++) {
                Point q = new Point (p.X + offset [dir, 0], p.Y + offset [dir, 1]);
                if (q.X < 0 || q.X >= width || q.Y < 0 || q.Y >= height || dist [q.X, q.Y] > 0 || grid [q.X, q.Y] != 0 && grid [q.X, q.Y] != value)
                    continue;
                dist [q.X, q.Y] = dist [p.X, p.Y] + 1;
                queue [queueLast++] = q;
            }
        }
        if (dist [p2.X, p2.Y] == 0)
            return false;
        Point tmp = new Point (p2.X, p2.Y);
        grid [tmp.X, tmp.Y] = value;
        for (int next = dist [tmp.X, tmp.Y] - 1; next > 0; next--) {
            int dirIndex = random.Next (24);
            for (int i = 0; i < 4; i++) {
                int dir = dirRandom [dirIndex, i];
                Point neighbor = new Point (tmp.X + offset [dir, 0], tmp.Y + offset [dir, 1]);
                if (neighbor.X < 0 || neighbor.X >= width || neighbor.Y < 0 || neighbor.Y >= height || dist [neighbor.X, neighbor.Y] != next)
                    continue;
                tmp = neighbor;
                grid [tmp.X, tmp.Y] = value;
                break;
            }
        }
        return true;
    }

    static void FillGaps(int[,] grid) {
        List<Point> missing = new List<Point> ();
        bool[,] inList = new bool[width, height];
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                if (grid [x, y] == 0 && !FillDoubleNeighbor (grid, x, y, missing, inList) && GetNeighborValues (grid, x, y) > 0 && !inList [x, y]) {
                    missing.Add (new Point (x, y));
                    inList [x, y] = true;
                }
            }
        }

        while (missing.Count > 0) {
            bool forceBorder = true;
            for (int i = missing.Count - 1; i >= 0; i--) {
                Point p = missing [i];
                if (grid [p.X, p.Y] != 0)
                    missing.RemoveAt (i);
                else {
                    int neighborValuesCount = GetNeighborValues (grid, p.X, p.Y);
                    if (neighborValuesCount == 1) {
                        grid [p.X, p.Y] = neighborValues [0];

                        if (p.X > 0 && grid [p.X - 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X - 1, p.Y, missing, inList) && !inList [p.X - 1, p.Y]) {
                            missing.Add (new Point (p.X - 1, p.Y));
                            inList [p.X - 1, p.Y] = true;
                        }
                        if (p.X + 1 < width && grid [p.X + 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X + 1, p.Y, missing, inList) && !inList [p.X + 1, p.Y]) {
                            missing.Add (new Point (p.X + 1, p.Y));
                            inList [p.X + 1, p.Y] = true;
                        }
                        if (p.Y > 0 && grid [p.X, p.Y - 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y - 1, missing, inList) && !inList [p.X, p.Y - 1]) {
                            missing.Add (new Point (p.X, p.Y -+ 1));
                            inList [p.X, p.Y - 1] = true;
                        }
                        if (p.Y + 1 < height && grid [p.X, p.Y + 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y + 1, missing, inList) && !inList [p.X, p.Y + 1]) {
                            missing.Add (new Point (p.X, p.Y + 1));
                            inList [p.X, p.Y + 1] = true;
                        }
                        forceBorder = false;
                    }
                }
            }
            if (forceBorder) {
                for (int i = missing.Count - 1; i >= 0; i--) {
                    Point p = missing [i];
                    if (grid [p.X, p.Y] != 0)
                        missing.RemoveAt (i);
                    else {
                        int neighborValuesCount = GetNeighborValues (grid, p.X, p.Y);
                        if (neighborValuesCount > 1) {
                            grid [p.X, p.Y] = neighborValues [random.Next (neighborValuesCount)];

                            if (p.X > 0 && grid [p.X - 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X - 1, p.Y, missing, inList) && !inList [p.X - 1, p.Y]) {
                                missing.Add (new Point (p.X - 1, p.Y));
                                inList [p.X - 1, p.Y] = true;
                            }
                            if (p.X + 1 < width && grid [p.X + 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X + 1, p.Y, missing, inList) && !inList [p.X + 1, p.Y]) {
                                missing.Add (new Point (p.X + 1, p.Y));
                                inList [p.X + 1, p.Y] = true;
                            }
                            if (p.Y > 0 && grid [p.X, p.Y - 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y - 1, missing, inList) && !inList [p.X, p.Y - 1]) {
                                missing.Add (new Point (p.X, p.Y -+ 1));
                                inList [p.X, p.Y - 1] = true;
                            }
                            if (p.Y + 1 < height && grid [p.X, p.Y + 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y + 1, missing, inList) && !inList [p.X, p.Y + 1]) {
                                missing.Add (new Point (p.X, p.Y + 1));
                                inList [p.X, p.Y + 1] = true;
                            }
                            break;
                        }
                    }
                }
            }
        }
    }

    static bool FillDoubleNeighbor(int[,] grid, int x, int y, List<Point> missing, bool[,] inList) {
        int neighborValuesCount = GetNeighborValues (grid, x, y);
        if (neighborValuesCount > 1) {
            for (int i = 0; i < neighborValuesCount; i++) {
                for (int j = i + 1; j < neighborValuesCount; j++) {
                    if (neighborValues [i] == neighborValues [j]) {
                        grid [x, y] = neighborValues [i];
                        for (int dir = 0; dir < 4; dir++) {
                            int x_ = x + offset [dir, 0];
                            int y_ = y + offset [dir, 1];
                            if (x_ >= 0 && x_ < width && y_ >= 0 && y_ < height && grid [x_, y_] == 0 && !FillDoubleNeighbor (grid, x_, y_, missing, inList) && !inList [x_, y_]) {
                                missing.Add (new Point (x_, y_));
                                inList [x_, y_] = true;
                            }
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static int[] neighborValues = new int[4];
    static int GetNeighborValues(int[,] grid, int x, int y) {
        int index = 0;
        if (x > 0 && grid [x - 1, y] != 0)
            neighborValues [index++] = grid [x - 1, y];
        if (x + 1 < width && grid [x + 1, y] != 0)
            neighborValues [index++] = grid [x + 1, y];
        if (y > 0 && grid [x, y - 1] != 0)
            neighborValues [index++] = grid [x, y - 1];
        if (y + 1 < height && grid [x, y + 1] != 0)
            neighborValues [index++] = grid [x, y + 1];
        return index;
    }

    static int[,] offset = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static double ScoreGrid(int[,] grid) {
        double[] area = new double[k];
        double[] perimeter = new double[k];

        for (int x = 0; x < width; x++) {
            perimeter [grid [x, 0] - 1]++;
            perimeter [grid [x, height - 1] - 1]++;
            for (int y = 0; y < height; y++) {
                area [grid [x, y] - 1]++;
                if (x + 1 < width && grid [x, y] != grid [x + 1, y]) {
                    perimeter [grid [x, y] - 1]++;
                    perimeter [grid [x + 1, y] - 1]++;
                }
                if (y + 1 < height && grid [x, y] != grid [x, y + 1]) {
                    perimeter [grid [x, y] - 1]++;
                    perimeter [grid [x, y + 1] - 1]++;
                }
            }
        }
        for (int y = 0; y < height; y++) {
            perimeter [grid [0, y] - 1]++;
            perimeter [grid [width - 1, y] - 1]++;
        }

        double score = 0;
        for (int i = 0; i < k; i++) {
            score += area [i] / (perimeter [i] * perimeter [i]);
        }
        return score;
    }

    struct Point {
        public int X;
        public int Y;

        public Point(int x, int y) {
            this.X = x;
            this.Y = y;
        }

        public override string ToString ()
        {
            return X + "/" + Y;
        }
    }
}