どくぬまのしれん - normal

code.cs

using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace NotFounds
{
    public class CellBoard
    {
        public enum Cell
        {
            Enemy,
            Plus,
            Minus,
            None
        }
        private Cell[,] board;
        public int W { get; private set; }
        public int H { get; private set; }
        public CellBoard(int w, int h)
        {
            W = w;
            H = h;
            board = new Cell[w, h];
        }
        public Cell this[int x, int y]
        {
            get
            {
                if (!CheckAlign(x, y)) new IndexOutOfRangeException();
                return board[x, y];
            }
            set
            {
                if (!CheckAlign(x, y)) new IndexOutOfRangeException();
                board[x, y] = value;
            }
        }
        private bool CheckAlign(int x, int y)
        {
            if (x < 0 || x >= W) return false;
            if (y < 0 || y >= H) return false;
            return true;
        }

        private List<State> GetNext(State now)
        {
            var dxy = new [] { 1, 0, -1, 0, 1 };
            if (now.HP <= 0) return new List<State>();

            var ret = new List<State>();
            for (int i = 0; i < 4; ++i)
            {
                var nx = now.X + dxy[i];
                var ny = now.Y + dxy[i + 1];
                if (!CheckAlign(nx, ny)) continue;
                if (now.Visited[nx, ny]) continue;
                if (this[nx, ny] == Cell.Enemy) continue;

                var hp = 0;
                if (this[nx, ny] == Cell.Plus) hp = 1;
                if (this[nx, ny] == Cell.Minus) hp = -1;
                var next = new State(new Point(nx, ny), now.HP + hp, now.Path + "RULD"[i]);
                for (int x = 0; x < 10; ++x)
                    for (int y = 0; y < 10; ++y)
                        next.Visited[x, y] = now.Visited[x, y];
                next.Visited[nx, ny] = true;
                ret.Add(next);
            }
            return ret;
        }

        public void ChokudaiSearch(int sx, int sy, int gx, int gy, int beam = 1000)
        {
            var dxy = new [] { 1, 0, -1, 0, 1 };
            var que = new IntervalHeap<State>[110];
            var initState = new State(new Point(sx, sy), 36); initState.Visited[sx, sy] = true;
            que[0] = new IntervalHeap<State>();
            que[0].Add(initState);
            for (int i = 1; i <= 100; ++i) que[i] = new IntervalHeap<State>();
            while (true)
            {
                for (int t = 0; t < 100; ++t)
                {
                    for (int i = 0; i < beam; ++i)
                    {
                        if (!que[t].Any()) break;
                        var now = que[t].RemoveMax();

                        var nexts = GetNext(now);
                        foreach (var next in nexts)
                        {
                            if (this[next.X, next.Y] == Cell.Enemy) continue;
                            if (next.X == gx && next.Y == gy)
                            {
                                if (next.HP >= 50)
                                {
                                    WriteLine($"{next.HP}: {next.Path}");
                                }
                            }
                            else
                            {
                                que[t + 1].Add(next);
                            }
                        }
                    }
                }
            }
        }

        private class State : IComparable<State>
        {
            public Point Pos { get; set; }
            public int HP { get; set; }
            public string Path { get; set; }
            public bool[,] Visited { get; set; }
            public State(Point pos, int hp, string path, bool[,] v) { Pos = pos; HP = hp; Path = path; Visited = v; }
            public State(Point pos, int hp, string path) { Pos = pos; HP = hp; Path = path; Visited = new bool[10, 10]; }
            public State(Point pos, int hp) { Pos = pos; HP = hp; Path = ""; Visited = new bool[10, 10]; }
            public int X { get { return this.Pos.X; } }
            public int Y { get { return this.Pos.Y; } }
            public int CompareTo(State obj)
            {
                return this.HP - obj.HP;
            }
        }
        private class Point
        {
            public int X { get; set; }
            public int Y { get; set; }
            public Point(int x, int y) { X = x; Y = y; }
        }
    }

    public class IntervalHeap<T> where T : IComparable<T>
    {
        private List<Node<T>> heap = new List<Node<T>>();
        private int n = 0;

        public IntervalHeap() { }
        public IntervalHeap(int size)
        {
            if (size <= 0) throw new ArgumentException("\"size\" must be greater than zero.");
            var capacity = size / 2 + 1;
            heap = new List<Node<T>>(capacity);
        }

        public void Add(T elem)
        {
            if (heap.Count * 2 == n) heap.Add(new Node<T>());

            if (n == 0)
            {
                heap[0].Left = elem;
                heap[0].Right = elem;
                n++;
                return;
            }
            else if (n == 1)
            {
                if (elem.CompareTo(heap[0].Left) < 0)
                    heap[0].Left = elem;
                else heap[0].Right = elem;
                n++;
                return;
            }
            else
            {
                var last = Last(n);
                bool isMinHeap;
                if (n % 2 == 1)
                {
                    // odd number of elements
                    isMinHeap = elem.CompareTo(heap[last].Left) < 0;
                }
                else
                {
                    // even number of elemnts
                    last++;
                    isMinHeap = elem.CompareTo(heap[Parent(n)].Left) <= 0;
                }

                if (isMinHeap)
                {
                    // fix min heap
                    var index = last;
                    var parent = Parent(index);
                    while (index != 0 && elem.CompareTo(heap[parent].Left) < 0)
                    {
                        heap[index].Left = heap[parent].Left;
                        index = parent;
                        parent = Parent(index);
                    }
                    heap[index].Left = elem;
                    n++;
                    if (n % 2 == 1)
                    {
                        // new size is odd, put dummy in last node
                        heap[last].Right = heap[last].Left;
                    }
                }
                else
                {
                    // fix max heap
                    var index = last;
                    var parent = Parent(index);
                    while (index != 0 && elem.CompareTo(heap[parent].Right) > 0)
                    {
                        heap[index].Right = heap[parent].Right;
                        index = parent;
                        parent = Parent(index);
                    }
                    heap[index].Right = elem;
                    n++;
                    if (n % 2 == 1)
                    {
                        // new size is odd, put dummy in last node
                        heap[last].Left = heap[last].Right;
                    }
                }
            }
        }

        public T GetMin()
        {
            if (n == 0) throw new InvalidOperationException("Heap is empty");
            return heap[0].Left;
        }

        public T GetMax()
        {
            if (n == 0) throw new InvalidOperationException("Heap is empty");
            return heap[0].Right;
        }

        public T RemoveMin()
        {
            if (n == 0) throw new InvalidOperationException("Heap is empty");

            var ret = heap[0].Left; // min element

            // restructure min heap part
            var last = Last(n);
            T elem; // element removed from last node
            if (n % 2 == 1)
            {
                // size is odd
                elem = heap[last].Left;
                last--;
            }
            else
            {
                // size is even
                elem = heap[last].Right;
                heap[last].Right = heap[last].Left;
            }
            n--;

            // find place for elem starting at root
            var index = 0; // current node of heap
            var child = 1; // left child of index
            while (child <= last)
            {
                // left child's left side should be smaller than right child's left side
                if (child < last && heap[child].Left.CompareTo(heap[child + 1].Left) > 0)
                    child++;

                // can we put y in heap[index]
                if (elem.CompareTo(heap[child].Left) <= 0)
                    break; // yes

                // no
                // move child up
                heap[index].Left = heap[child].Left;
                if (elem.CompareTo(heap[child].Right) > 0)
                {
                    // swap elem and heap[child].right
                    var tmp = elem;
                    elem = heap[child].Right;
                    var newNode = new Node<T>(heap[child].Left, tmp);
                    heap[child] = newNode;
                }
                index = child;
                child = LeftChild(index);
            }
            if (index == last && n % 2 == 1)
                heap[last].Left = heap[last].Right;
            else
                heap[index].Left = elem;

            if (n == 1)
            {
                heap[0].Left = elem;
                heap[0].Right = elem;
            }

            return ret;
        }

        public T RemoveMax()
        {
            if (n == 0) throw new InvalidOperationException("Heap is empty");

            var ret = heap[0].Right; // max element

            // restructure max heap part
            var last = Last(n);
            T elem; // element removed from last node
            if (n % 2 == 1)
            {
                // size is odd
                elem = heap[last].Left;
                last--;
            }
            else
            {
                // size is even
                elem = heap[last].Right;
                heap[last].Right = heap[last].Left;
            }
            n--;

            // find place for elem starting at root
            var index = 0; // current node of heap
            var child = 1; // left child of index
            while (child <= last)
            {
                // right child's right side should be smaller than left child's right side
                if (child < last && heap[child].Right.CompareTo(heap[child + 1].Right) < 0)
                    child++;

                // can we put elem in heap[index]?
                if (elem.CompareTo(heap[child].Right) >= 0)
                    break; // yes

                // no
                // move child up
                heap[index].Right = heap[child].Right;
                if (elem.CompareTo(heap[child].Left) < 0)
                {
                    // swap elem and heap[child].left
                    var tmp = elem;
                    elem = heap[child].Left;
                    var newNode = new Node<T>(tmp, heap[child].Right);
                    heap[child] = newNode;
                }
                index = child;
                child = LeftChild(index);
            }
            if (n != 1)
                heap[index].Right = elem;

            return ret;
        }

        public void Clear()
        {
            heap.Clear();
        }

        public bool Any()
        {
            return n > 0;
        }

        public bool IsEmpty()
        {
            return !Any();
        }

        public int Count
        {
            get { return n; }
        }

        public int Capacity
        {
            get { return heap.Count; }
        }

        public void TrimExcess()
        {
            var last = n / 2;
            var diff = heap.Count - last - 1;
            for (var i = 1; i < diff; ++i)
                heap.RemoveAt(i);
        }

        private int Parent(int i) { return i != 0 ? (i - 1) >> 1 : 0; }
        private int LeftChild(int i) { return (i << 1) + 1; }
        private int RightChild(int i) { return (i << 1) + 2; }
        private int Last(int n) { return n != 0 ? (n >> 1) + (n & 1) - 1 : 0; }

        private class Node<NT> where NT : IComparable<T>
        {
            public Node() { }
            public Node(NT a, NT b) { Left = a; Right = b; }
            public NT Left { get; set; }
            public NT Right { get; set; }
        }
    }

    public class Program
    {
        public static void Main()
        {
            var input = new int[10][] {
                new []{-1,1,1,-1,-1,1,1,-1,-1,1},
                new []{1,4,1,3,-1,-1,-1,-1,-1,-1,-1},
                new []{-1,-1,-1,1,1,-1,1,-1,1,1},
                new []{1,3,-1,-1,1,-1,1,-1,1,-1},
                new []{-1,1,1,-1,-1,-1,-1,3,1,-1},
                new []{1,-1,1,-1,-1,1,-1,1,-1,1},
                new []{-1,3,-1,-1,-1,1,-1,-1,-1,1},
                new []{-1,1,-1,1,1,-1,1,-1,-1,-1},
                new []{-1,1,-1,-1,-1,1,1,-1,5,1},
                new []{-1,-1,1,1,-1,-1,-1,1,-1,-1}
            };
            var board = new CellBoard(10, 10);
            int sx = 0, sy = 0, gx = 0, gy = 0;
            for (int i = 0; i < 10; ++i)
            {
                for (int j = 0; j < 10; ++j)
                {
                    switch (input[i][j])
                    {
                        case -1:
                            board[j, i] = CellBoard.Cell.Minus;
                            break;
                        case 1:
                            board[j, i] = CellBoard.Cell.Plus;
                            break;
                        case 3:
                            board[j, i] = CellBoard.Cell.Enemy;
                            break;
                        case 4:
                            board[j, i] = CellBoard.Cell.None;
                            sx = j;
                            sy = i;
                            break;
                        case 5:
                            board[j, i] = CellBoard.Cell.None;
                            gx = j;
                            gy = i;
                            break;
                    }
                }
            }
            board.ChokudaiSearch(sx, sy, gx, gy);
        }
    }
}

HP: Direction

51: RDRRDRRUUULLLLLLDDDDDRURDDDLDDRRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDDRURDDDLDRDRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDRDRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURDRRUULURRRUUURDDDDDDL