Last active
September 24, 2018 16:24
-
-
Save NotFounds/d086992284ce27030e2fdf1edecf3ba2 to your computer and use it in GitHub Desktop.
どくぬまのしれん - normal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
HP: Direction
51: RDRRDRRUUULLLLLLDDDDDRURDDDLDDRRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDDRURDDDLDRDRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDRDRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURRDRUULURRRUUURDDDDDDL
51: RDRRDRRUUULLLLLLDDDDRRDDDLDDRRUURDRRUULURRRUUURDDDDDDL