Submission #68709741

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Formats.Asn1;
using System.Linq;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.Text;

public class Solution
{
    public const int TIME_LIMIT = 1700;
    private static Random random = new Random(0);
    public static void Main()
    {
        int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Stopwatch sw = Stopwatch.StartNew();
        Board.Size = inputs[0];
        int m = inputs[1];
        int k = inputs[2];
        Board.InitGrid();
        Board board = new Board();
        board.Robots = Enumerable.Range(0, m).Select(i => new Robot { ID = i }).ToList();
        board.Waxed = new bool[Board.Size * Board.Size];
        Robot.RobotActions = Enumerable.Range(0, m).Select(i => new int[k]).ToArray();
        foreach (Robot r in board.Robots)
        {
            inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            r.Location = Board.Grid[inputs[1], inputs[0]];
            board.Waxed[r.Location.ID] = true;
        }
        board.WaxedCount = board.Waxed.Count(b => b);

        for (int y = 0; y < Board.Size; y++)
        {
            string line = Console.ReadLine();
            for (int x = 0; x < line.Length; x++)
            {
                if (line[x] == '1')
                {
                    Board.Grid[x, y].Neighbors[0] = Board.Grid[x, y];
                    Board.Grid[x + 1, y].Neighbors[2] = Board.Grid[x + 1, y];
                }
            }
        }
        for (int y = 0; y < Board.Size - 1; y++)
        {
            string line = Console.ReadLine();
            for (int x = 0; x < line.Length; x++)
            {
                if (line[x] == '1')
                {
                    Board.Grid[x, y].Neighbors[1] = Board.Grid[x, y];
                    Board.Grid[x, y + 1].Neighbors[3] = Board.Grid[x, y + 1];
                }
            }
        }
        Board.InitDistances();

        string actionString = "RDLUS";
        InitActions(board);
        Board solution = WaxBoard(board, null);
        Console.Error.WriteLine("initial solution: " + solution.Depth + " @" + sw.ElapsedMilliseconds + " ms");
        HashSet<Board> revertedTo = new();
        while (sw.ElapsedMilliseconds < TIME_LIMIT)
        {
            Board prev = solution.Parent;
            Cell lastFill = null;
            foreach (Cell c in Board.Grid)
            {
                if (!prev.Waxed[c.ID]) lastFill = c;
            }
            Board b = board;
            while (prev.Parent != null)
            {
                if (prev.Robots.Any(r => r.Location.Neighbors.Contains(lastFill))) b = prev;
                prev = prev.Parent;
            }
            if (!revertedTo.Add(b))
            {
                b = board;
                for (int i = 0; i < 5; i++) b = board.Expand().OrderBy(b => random.NextDouble()).First();
            }
            else if (b != board) b = b.Expand().First(e => e.Waxed[lastFill.ID]);
            Console.Error.WriteLine(sw.ElapsedMilliseconds + "ms: revert to " + b.Depth);
            Board refill = WaxBoard(b, sw);
            Console.Error.WriteLine("refill length: " + refill?.Depth);
            if (refill != null && refill.Depth < solution.Depth)
            {
                Console.Error.WriteLine("shorten: " + solution.Depth + " => " + refill.Depth);
                solution = refill;
            }
        }

        // try to fill last cell with different action
        bool improved = true;
        while (improved)
        {
            improved = false;
            Board prev = solution.Parent;
            Cell lastFill = null;
            foreach (Cell c in Board.Grid)
            {
                if (!prev.Waxed[c.ID]) lastFill = c;
            }
            List<Board> candidates = new();
            List<Board> path = new();
            while (prev.Parent != null)
            {
                path.Add(prev);
                if (prev.Robots.Any(r => r.Location.Neighbors.Contains(lastFill))) candidates.Add(prev);
                prev = prev.Parent;
            }
            path.Add(prev);
            path.Reverse();
            foreach (Board c in candidates.Reverse<Board>())
            {
                foreach (Robot r in c.Robots.Where(ro => ro.Location.Neighbors.Contains(lastFill)))
                {
                    int a1 = r.Location.Neighbors.ToList().IndexOf(lastFill);
                    int a2 = lastFill.Neighbors.ToList().IndexOf(r.Location);
                    List<int> a1Cand = Enumerable.Range(0, k).Where(i => r.Actions[i] == a1).ToList();
                    List<int> a2Cand = Enumerable.Range(0, k).Where(i => r.Actions[i] == a2).ToList();
                    foreach (int a1Take in a2Cand)
                    {
                        foreach (int a2Take in a1Cand)
                        {
                            Board inserted = InsertAction(c, path, r, a1Take, a2Take);
                            if (inserted != null && inserted.Depth < solution.Depth)
                            {
                                Console.Error.WriteLine("postprecessing: " + solution.Depth + " => " + inserted.Depth);
                                improved = true;
                                solution = inserted;
                                goto hasImproved;
                            }
                        }
                    }
                    List<int> empty = Enumerable.Range(0, k).Where(i => r.Actions[i] == 4).ToList();
                    for (int e = 0; e + 1 < empty.Count; e += 2)
                    {
                        r.Actions[empty[e]] = a1;
                        r.Actions[empty[e + 1]] = a2;
                        Board inserted = InsertAction(c, path, r, empty[e], empty[e + 1]);
                        if (inserted != null && inserted.Depth < solution.Depth)
                        {
                            Console.Error.WriteLine("postprecessing: " + solution.Depth + " => " + inserted.Depth);
                            improved = true;
                            solution = inserted;
                            goto hasImproved;
                        }
                        else
                        {
                            r.Actions[empty[e]] = 4;
                            r.Actions[empty[e + 1]] = 4;
                        }
                    }
                }
            }
        hasImproved:;
        }

        for (int actionId = 0; actionId < k; actionId++)
        {
            Console.WriteLine(string.Join(" ", solution.Robots.Select(r => actionString[r.Actions[actionId]])));
        }
        List<int> actions = new();
        while (solution.Parent != null)
        {
            actions.Add(solution.Action);
            solution = solution.Parent;
        }
        actions.Reverse();
        foreach (int a in actions) Console.WriteLine(a);
    }

    private static Board InsertAction(Board board, List<Board> path, Robot r, int action1, int action2)
    {
        int index = path.IndexOf(board);
        Board result = path[0];
        for (int i = 1; i <= index; i++) result = new Board(result, path[i].Action);
        result = new Board(result, action1);
        result = new Board(result, action2);
        for (int i = index + 1; i < path.Count; i++) result = new Board(result, path[i].Action);
        if (result.WaxedCount != Board.Size * Board.Size) return null;
        while (result.Parent.WaxedCount == Board.Size * Board.Size) result = result.Parent;
        return result;
    }

    private static Board WaxBoard(Board board, Stopwatch sw)
    {
        List<Board> beam = new() { board };
        for (int depth = 1; sw == null || sw.ElapsedMilliseconds < TIME_LIMIT; depth++)
        {
            beam = beam.SelectMany(b => b.Expand()).OrderByDescending(b => 0.01 * random.NextDouble() + b.Score()).Take(3).ToList();
            if (beam[0].WaxedCount == Board.Size * Board.Size) return beam[0];
        }
        return null;
    }

    private static void InitActions(Board board)
    {
        foreach (Robot r in board.Robots)
        {
            while (r.Actions.Distinct().Count() < 4)
            {
                for (int i = 0; i < r.Actions.Length; i++) r.Actions[i] = Math.Min(i, 4);
                //for (int i = 0; i < r.Actions.Length; i++) r.Actions[i] = random.Next(4);// Math.Min(i, 4);
            }
        }
    }
}

public class Board
{
    public static int Size;
    public List<Robot> Robots = new();
    public static Cell[,] Grid;
    public bool[] Waxed;
    public int WaxedCount;
    public Board Parent;
    public int Action;
    public int Depth;

    public Board() { }
    public Board(Board parent, int action)
    {
        this.Parent = parent;
        this.Action = action;
        this.Depth = parent.Depth + 1;
        this.WaxedCount = parent.WaxedCount;
        this.Waxed = parent.Waxed.ToArray();
        this.Robots = parent.Robots.Select(r => new Robot(r, action)).ToList();
        foreach (Robot r in Robots)
        {
            if (!Waxed[r.Location.ID])
            {
                Waxed[r.Location.ID] = true;
                WaxedCount++;
            }
        }
    }

    public static void InitGrid()
    {
        Grid = new Cell[Board.Size, Board.Size];
        for (int x = 0; x < Board.Size; x++)
        {
            for (int y = 0; y < Board.Size; y++)
            {
                Grid[x, y] = new Cell(x, y);
            }
        }
        foreach (Cell cell in Grid) cell.InitNeighbors(Grid);
    }

    public static void InitDistances()
    {
        foreach (Cell cell in Grid) cell.InitDistances();
    }

    public IEnumerable<Board> Expand()
    {
        for (int i = 0; i < 4; i++)
        {
            yield return new Board(this, i);
        }
    }

    public double Score()
    {
        double result = 1e6 * WaxedCount;
        result += 0.3 * Robots.Select(r => r.Location).Distinct().Count();
        int closest = 1000;
        foreach (Cell c in Board.Grid)
        {
            if (!Waxed[c.ID])
            {
                closest = Math.Min(closest, Robots.Min(r => r.Location.Dist[c.ID]));
                int openNeighbors = c.DistinctNeighbors.Count(n => !Waxed[n.ID]);
                if (openNeighbors == 0) result -= 3;
                else if (openNeighbors == 1) result -= 1;
            }
        }
        foreach (Robot r in Robots)
        {
            int unwaxedNeighbors = r.Location.DistinctNeighbors.Count(n => !Waxed[n.ID]);
            if (unwaxedNeighbors > 0) result += 0.01 * (4 - unwaxedNeighbors);
        }
        result -= closest;
        return result;
    }
}

public class Robot
{
    public int ID;
    public Cell Location;
    public static int[][] RobotActions;
    public int[] Actions => RobotActions[ID];

    public Robot() { }
    public Robot(Robot r, int action)
    {
        this.ID = r.ID;
        this.Location = r.Location.Neighbors[Actions[action]];
    }

    public override string ToString() => ID + ": " + Location;
}

public class Cell
{
    public int X;
    public int Y;
    public int ID => X + Y * Board.Size;
    public Cell[] Neighbors = new Cell[5];
    public Cell[] DistinctNeighbors;
    public int[] Dist;

    public Cell(int x, int y)
    {
        X = x;
        Y = y;
    }

    private static int[] dx = { 1, 0, -1, 0, 0 };
    private static int[] dy = { 0, 1, 0, -1, 0 };
    public void InitNeighbors(Cell[,] grid)
    {
        for (int dir = 0; dir < dx.Length; dir++)
        {
            int x_ = X + dx[dir];
            int y_ = Y + dy[dir];
            if (x_ < 0 || x_ >= Board.Size || y_ < 0 || y_ >= Board.Size) Neighbors[dir] = this;
            else Neighbors[dir] = grid[x_, y_];
        }
        DistinctNeighbors = Neighbors.Where(n => n != this).Distinct().ToArray();
    }

    public void InitDistances()
    {
        Dist = new int[Board.Size * Board.Size];
        Array.Fill(Dist, 10000);
        Dist[ID] = 0;
        Queue<Cell> queue = new Queue<Cell>();
        queue.Enqueue(this);
        while (queue.Count > 0)
        {
            Cell c = queue.Dequeue();
            foreach (Cell n in c.Neighbors)
            {
                if (Dist[n.ID] < 10000) continue;
                Dist[n.ID] = 1 + Dist[c.ID];
                queue.Enqueue(n);
            }
        }
    }

    public override string ToString() => X + "/" + Y;
}

Submission Info

Judge Result