288 lines
7.8 KiB
Python
288 lines
7.8 KiB
Python
import sys
|
|
import math
|
|
from collections import deque
|
|
|
|
WALL = '#'
|
|
EMPTY = '.'
|
|
FOG = '?'
|
|
COMMAND = 'C'
|
|
START = 'T'
|
|
|
|
LEFT = 'LEFT'
|
|
RIGHT = 'RIGHT'
|
|
UP = 'UP'
|
|
DOWN = 'DOWN'
|
|
|
|
TARGET_NODE = {
|
|
COMMAND: None,
|
|
START: None,
|
|
'explore': None
|
|
}
|
|
|
|
|
|
class Node:
|
|
def __init__(self, r, c, g=0, h=0, parent=None, maze=None):
|
|
if maze is None:
|
|
maze = [[]]
|
|
self._maze = maze
|
|
self.r = r
|
|
self.c = c
|
|
self.g = g
|
|
self.h = h
|
|
self.parent = parent
|
|
self.colored = False
|
|
|
|
def __str__(self):
|
|
return 'Node({}, {}, {})'.format(self.r, self.c, self.type)
|
|
|
|
def __repr__(self):
|
|
return self.__str__()
|
|
|
|
@property
|
|
def f(self):
|
|
return self.g + self.h
|
|
|
|
def __lt__(self, other):
|
|
return self.f < other.f
|
|
|
|
def __le__(self, other):
|
|
return self.f <= other.f
|
|
|
|
def __gt__(self, other):
|
|
return self.f > other.f
|
|
|
|
def __ge__(self, other):
|
|
return self.f >= other.f
|
|
|
|
def __eq__(self, other):
|
|
return self.r == other.r and self.c == other.c
|
|
|
|
@property
|
|
def type(self):
|
|
return self._maze[self.r][self.c]
|
|
|
|
def direction_to(self, other):
|
|
if other.r > self.r:
|
|
return DOWN
|
|
elif other.r < self.r:
|
|
return UP
|
|
elif other.c > self.c:
|
|
return RIGHT
|
|
elif other.c < self.c:
|
|
return LEFT
|
|
|
|
def distance_2_to(self, other):
|
|
return (self.c - other.c) ** 2 + (self.r - other.r) ** 2
|
|
|
|
|
|
def main():
|
|
# r: number of rows.
|
|
# c: number of columns.
|
|
# a: number of rounds between the time the alarm countdown is activated and the time the alarm goes off.
|
|
rows, columns, a = [int(i) for i in input().split()]
|
|
target = COMMAND
|
|
|
|
# visited = []
|
|
# current_node = None
|
|
# last_intersection = None
|
|
steps_remaining = 0
|
|
while True:
|
|
# kr: row where Kirk is located.
|
|
# kc: column where Kirk is located.
|
|
kr, kc = [int(i) for i in input().split()]
|
|
maze = []
|
|
start_node = None
|
|
command_node = None
|
|
for i in range(rows):
|
|
row = input()
|
|
|
|
if START in row and not start_node:
|
|
start_node = Node(i, row.index(START), maze=maze)
|
|
TARGET_NODE[START] = start_node
|
|
if COMMAND in row and not command_node:
|
|
command_node = Node(i, row.index(COMMAND), maze=maze)
|
|
TARGET_NODE[COMMAND] = command_node
|
|
|
|
maze.append(row)
|
|
|
|
current_node = Node(kr, kc, 0, 0, None, maze=maze)
|
|
|
|
if steps_remaining > 0:
|
|
steps_remaining -= 1
|
|
perr('steps_remaining', steps_remaining)
|
|
|
|
else:
|
|
if current_node.type == COMMAND:
|
|
target = START
|
|
perr(maze)
|
|
|
|
if target == COMMAND:
|
|
path_target = remaining_exploration(maze, current_node, rows, columns)
|
|
if not path_target:
|
|
path_target = TARGET_NODE[COMMAND]
|
|
|
|
else:
|
|
path_target = TARGET_NODE[START]
|
|
|
|
path = []
|
|
|
|
perr('TARGET', target)
|
|
perr('Algorithm target', path_target)
|
|
perr('current', current_node)
|
|
|
|
found = a_star_search(current_node, path_target, maze, rows, columns)
|
|
|
|
walker = found
|
|
perr('walker', walker)
|
|
while walker is not None:
|
|
path.append(walker)
|
|
walker = walker.parent
|
|
|
|
path.reverse()
|
|
perr('path', path)
|
|
|
|
prev = None
|
|
for node in path:
|
|
if prev:
|
|
print(prev.direction_to(node))
|
|
steps_remaining = len(path) - 2
|
|
prev = node
|
|
|
|
|
|
def bfs_search(current_node, path_target, maze, rows, columns):
|
|
perr('STARTING BFS')
|
|
queue = deque([current_node])
|
|
visited = []
|
|
found = None
|
|
|
|
while len(queue) > 0 and not found:
|
|
item = queue.popleft()
|
|
visited.append(item)
|
|
successors = generate_successors(maze, item, rows, columns)
|
|
perr('visited', visited)
|
|
for s in successors:
|
|
perr('s', s)
|
|
if s == path_target:
|
|
perr('FOUND TARGET')
|
|
found = s
|
|
break
|
|
elif s.type == '#':
|
|
visited.append(s)
|
|
elif path_target.type != COMMAND and s.type == COMMAND:
|
|
visited.append(s)
|
|
else:
|
|
skip = False
|
|
for o in queue:
|
|
if s == o and o < s:
|
|
skip = True
|
|
break
|
|
|
|
for c in visited:
|
|
if s == c and c < s:
|
|
skip = True
|
|
break
|
|
if not skip:
|
|
queue.append(s)
|
|
|
|
return found
|
|
|
|
|
|
def a_star_search(current_node, path_target, maze, rows, columns):
|
|
perr('STARTING A*')
|
|
open_list = deque([current_node])
|
|
closed_list = []
|
|
found = None
|
|
|
|
# A* loop
|
|
while len(open_list) > 0 and not found:
|
|
q = min(open_list)
|
|
open_list.remove(q)
|
|
successors = generate_successors(maze, q, rows, columns)
|
|
perr('q', q)
|
|
for s in successors:
|
|
if s == path_target:
|
|
perr('FOUND TARGET')
|
|
found = s
|
|
break
|
|
|
|
if s.type == '#':
|
|
h = math.inf
|
|
elif path_target.type != COMMAND and s.type == COMMAND:
|
|
h = math.inf
|
|
else:
|
|
# TODO: need a better heuristic for last 2 levels (zigzags are baaad)
|
|
h = s.distance_2_to(path_target)
|
|
s.h = h
|
|
|
|
skip = False
|
|
for o in open_list:
|
|
if s == o and o < s:
|
|
skip = True
|
|
break
|
|
|
|
for c in closed_list:
|
|
if s == c and c < s:
|
|
skip = True
|
|
break
|
|
|
|
if not skip:
|
|
open_list.append(s)
|
|
|
|
closed_list.append(q)
|
|
|
|
perr('FOUND A* PATH')
|
|
return found
|
|
|
|
|
|
def generate_successors(maze, node, max_rows, max_columns, with_walls=False, with_fog=False):
|
|
successors = []
|
|
successor_g = node.g + 1
|
|
|
|
if (node.c - 1) >= 0:
|
|
succ = Node(node.r, node.c - 1, g=successor_g, parent=node, maze=maze)
|
|
if not (succ.type == WALL and not with_walls or succ.type == FOG and not with_fog):
|
|
successors.append(succ)
|
|
|
|
if (node.r + 1) < max_rows:
|
|
succ = Node(node.r + 1, node.c, g=successor_g, parent=node, maze=maze)
|
|
if not (succ.type == WALL and not with_walls or succ.type == FOG and not with_fog):
|
|
successors.append(succ)
|
|
|
|
if (node.c + 1) < max_columns:
|
|
succ = Node(node.r, node.c + 1, g=successor_g, parent=node, maze=maze)
|
|
if not (succ.type == WALL and not with_walls or succ.type == FOG and not with_fog):
|
|
successors.append(succ)
|
|
|
|
if (node.r - 1) >= 0:
|
|
succ = Node(node.r - 1, node.c, g=successor_g, parent=node, maze=maze)
|
|
if not (succ.type == WALL and not with_walls or succ.type == FOG and not with_fog):
|
|
successors.append(succ)
|
|
|
|
return successors
|
|
|
|
|
|
def remaining_exploration(maze, node, max_rows, max_columns):
|
|
remaining = deque([node])
|
|
visited = []
|
|
while len(remaining) > 0:
|
|
cur = remaining.popleft()
|
|
visited.append(cur)
|
|
neighbors = generate_successors(maze, cur, max_rows, max_columns, with_walls=False, with_fog=True)
|
|
for n in neighbors:
|
|
if n.type == FOG:
|
|
if cur.type == COMMAND:
|
|
return cur.parent
|
|
else:
|
|
return cur
|
|
if n not in remaining and n not in visited:
|
|
remaining.append(n)
|
|
|
|
return None
|
|
|
|
|
|
def perr(*values, **kwargs):
|
|
print(*values, file=sys.stderr, flush=True, **kwargs)
|
|
|
|
if __name__ == '__main__':
|
|
main()
|