Skip to content

Instantly share code, notes, and snippets.

@NotFounds
Last active September 24, 2018 16:24
Show Gist options
  • Save NotFounds/d086992284ce27030e2fdf1edecf3ba2 to your computer and use it in GitHub Desktop.
Save NotFounds/d086992284ce27030e2fdf1edecf3ba2 to your computer and use it in GitHub Desktop.
どくぬまのしれん - normal
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);
}
}
}
@NotFounds
Copy link
Author

HP: Direction

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment