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()