Submission #65209566

---

Source Code Expand

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

public class Solution
{
    public const int TIME_LIMIT = 1700;
    public static void Main()
    {
        int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        Board.Size = inputs[0];
        Board.InitBoard();
        int m = inputs[1];
        List<Cell> path = new List<Cell>();
        for (int i = 0; i < m; i++)
        {
            inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            path.Add(Board.Grid[inputs[1], inputs[0]]);
        }
        Board.Path = path.ToArray();

        Board board = new Board() { Current = path[0], NextTarget = 1 };
        List<Board> beam = new List<Board> { board };
        Stopwatch sw = Stopwatch.StartNew();
        int beamWidth = 500;
        HashSet<Board> past = new HashSet<Board> { board };
        int expanded = 0;
        for (int depth = 1; ; depth++)
        {
            HashSet<Board> next = new HashSet<Board>();
            foreach (Board b in beam)
            {
                foreach (Board b2 in b.Expand())
                {
                    expanded++;
                    if (past.Add(b2)) next.Add(b2);
                }
            }
            beam = next.OrderByDescending(n => n.Score()).Take(beamWidth).ToList();
            int time = (int)sw.ElapsedMilliseconds;
            double shallExpand = (double)expanded / time * (TIME_LIMIT - time);
            beamWidth = (int)(shallExpand / (220.0 - depth) / 6.5);
            beamWidth = Math.Max(beamWidth, 100);
            beamWidth = Math.Min(beamWidth, 1000);
            if (beam[0].NextTarget == m)
            {
                foreach (string a in beam[0].GetActions()) Console.WriteLine(a);
                break;
            }
        }
        Console.Error.WriteLine(beam[0].GetActions().Count + "   - " + sw.ElapsedMilliseconds + " ms");
    }
}

public enum ActionType
{
    Move,
    Slide,
    Alter
}

public class Board : IEquatable<Board>
{
    public static int Size;
    public static int Area => Size * Size;
    public static Cell[,] Grid;
    public static Cell[] Path;
    public List<Cell> Block;
    public Board Parent;
    public int ActionDir;
    public ActionType ActionType;
    public Cell Current;
    public int NextTarget;
    public long Hash;

    public Board()
    {
        Block = new List<Cell>();
    }

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

    public Board(Board parent, int dir, ActionType actionType, Cell targetCell)
    {
        this.Parent = parent;
        this.ActionDir = dir;
        this.ActionType = actionType;
        this.Block = parent.Block;
        this.NextTarget = parent.NextTarget;
        this.Hash = parent.Hash;
        if (actionType == ActionType.Alter)
        {
            Block = new List<Cell>(Block);
            Current = parent.Current;
            if (Block.Contains(targetCell)) Block.Remove(targetCell);
            else Block.Add(targetCell);
            Hash ^= targetCell.WallHash;
        }
        else
        {
            Current = targetCell;
            if (Current == Path[NextTarget]) NextTarget++;
            Hash ^= this.Current.PositionHash ^ parent.Current.PositionHash ^ NextTarget ^ parent.NextTarget;
        }
    }

    public IEnumerable<Board> Expand()
    {
        for (int dir = 0; dir < 4; dir++)
        {
            Cell next = Current.Neighbors[dir];
            if (next == null) continue;
            yield return new Board(this, dir, ActionType.Alter, next);
            if (Block.Contains(next)) continue;
            yield return new Board(this, dir, ActionType.Move, next);
            while (next.Neighbors[dir] != null && !Block.Contains(next.Neighbors[dir])) next = next.Neighbors[dir];
            yield return new Board(this, dir, ActionType.Slide, next);
        }
    }

    public List<string> GetActions()
    {
        List<string> result = new List<string>();
        Board b = this;
        while (b.Parent != null)
        {
            result.Add(b.ActionType.ToString()[0] + " " + "DRUL"[b.ActionDir]);
            b = b.Parent;
        }
        result.Reverse();
        return result;
    }

    private static Dictionary<long, double> blockLookup = new Dictionary<long, double>();
    public double Score()
    {
        double result = 1000 * NextTarget;
        if (NextTarget < Path.Length) result -= Current.Dist(Path[NextTarget]);
        long blockKey = Hash ^ Current.PositionHash;
        if (blockLookup.ContainsKey(blockKey)) result += blockLookup[blockKey];
        else
        {
            double factor = 1;
            double blockScore = 0;
            for (int t = NextTarget; t < Path.Length; t++)
            {
                Cell target = Path[t];
                if (Block.Contains(target)) blockScore--;
                int dist = target.Dist(target.CloseCells.Last());
                foreach (Cell b in Block) dist = Math.Min(dist, b.Dist(target));
                blockScore -= factor * dist;
                factor *= 0.99;
            }
            blockLookup[blockKey] = blockScore;
            result += blockScore;
        }
        return result;
    }

    public override int GetHashCode() => Hash.GetHashCode();

    public bool Equals(Board board) => this.Hash == board.Hash;
}

public class Cell
{
    public int X;
    public int Y;
    public int ID => X * Board.Size + Y;
    public Cell[] Neighbors = new Cell[4];
    public Cell[] CloseCells;
    private static Random random = new Random(0);
    public long PositionHash;
    public long WallHash;
    public Cell(int x, int y)
    {
        this.X = x;
        this.Y = y;
        PositionHash = random.NextInt64();
        WallHash = random.NextInt64();
    }

    private static int[] dx = { 0, 1, 0, -1 };
    private static int[] dy = { 1, 0, -1, 0 };

    public void MakeNeighbors(Cell[,] grid)
    {
        for (int dir = 0; dir < dx.Length; dir++)
        {
            int x = this.X + dx[dir];
            int y = this.Y + dy[dir];
            if (x >= 0 && x < Board.Size && y >= 0 && y < Board.Size) Neighbors[dir] = grid[x, y];
        }
    }

    public void MakeCloseCells()
    {
        List<Cell> close = new List<Cell>();
        Queue<Cell> queue = new Queue<Cell>();
        bool[] visited = new bool[Board.Area];
        queue.Enqueue(this);
        visited[this.ID] = true;
        while (true)
        {
            Cell c = queue.Dequeue();
            foreach (Cell n in c.Neighbors)
            {
                if (n == null) goto stopLoop;
                if (visited[n.ID]) continue;
                close.Add(n);
                queue.Enqueue(n);
            }
        }
    stopLoop:
        if (close.Count == 0) close.Add(Neighbors.First(n => n != null));
        CloseCells = close.ToArray();
    }

    public int Dist(Cell cell)
    {
        return Math.Abs(X - cell.X) + Math.Abs(Y - cell.Y);
    }

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

Submission Info

Judge Result