import heapq import sys import time t0 = time.time() def log(*msg): print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr) class Queue(): def __init__(self): self.items = [] def __bool__(self): return bool(self.items) def __repr__(self): return str(self.items) def values(self): return (v for _, v in self.items) def put(self, item, priority): heapq.heappush(self.items, (priority, item)) def fput(self, item, priority): while priority in [p for p, _ in self.items]: priority += 1 self.put(item, priority) def get(self): return heapq.heappop(self.items)[1] class PathNode(tuple): def __new__(self, x, y, parent=None): n = tuple.__new__(self, (x, y)) n.parent = parent n.cost = 0 return n def __repr__(self): return f"<{self[0]}, {self[1]}, c:{self.cost}>" def ancestors(self): ancestors = [] p = self.parent while p: ancestors.insert(0, p) p = p.parent return ancestors class Waypoint(tuple): def __new__(self, x, y, neighbors=None): n = tuple.__new__(self, (x, y)) n.neighbors = neighbors or [] return n def __repr__(self): return f"<({self[0]},{self[1]}), n:{self.neighbors}>" MOVES = {(0, -1) : "UP", (0, 1): "DOWN", (-1, 0): "LEFT", (1, 0) : "RIGHT"} h, w, countdown = [int(i) for i in input().split()] UP = "UP" RIGHT = "RIGHT" DOWN = "DOWN" LEFT = "LEFT" MOVES = [UP, RIGHT, DOWN, LEFT] class Grid(): UNKNOWN = 0 WALL = 1 EMPTY = 2 VECT = {UP: (0,-1), RIGHT: (1,0), DOWN: (0,1), LEFT: (-1,0)} INV = {UP: DOWN, RIGHT: LEFT, LEFT: RIGHT, DOWN: UP} def __init__(self, w, h): self.w = w self.h = h self.cells = {(x, y): Grid.UNKNOWN for x in range(self.w) for y in range(self.h)} self.start = None self.control_room = None self.kirk = None self.neighbors = {p: self.get_neighbors(*p) for p in self.cells} self.waypoints = [] self.to_explore = None def update(self, kirk, scan): self.previous_pos = self.kirk self.kirk = kirk if not self.start: self.start = kirk for y, row in enumerate(scan): for x, c in enumerate(row): if c == "C": self.control_room = (x, y) self.cells[(x, y)] = {"#": Grid.WALL, "?": Grid.UNKNOWN}.get(c, Grid.EMPTY) if self.to_explore is not None: if self.cells[self.to_explore] != Grid.UNKNOWN: self.to_explore = None self.update_corners() def _repr_cell(self, p, show=[]): if p == self.kirk: return "T" elif p == self.start: return "S" elif p == self.control_room: return "C" elif self.cells[p] == Grid.WALL: return "#" elif p in show: return "x" elif self.cells[p] == Grid.EMPTY: return "." else: return "?" def graph(self, show=[]): return "\n".join(["".join([self._repr_cell((x, y), show) for x in range(self.w)]) for y in range(self.h)]) def set_visited(self, p): self.cells[p] = Grid.EMPTY def set_wall(self, p): self.cells[p] = Grid.WALL def unknown_gravity_center(self): wx, wy, wtotal = 0,0,0 for x, y in self.cells: if self.cells[(x, y)] == Grid.UNKNOWN: wx += x wy += y wtotal += 1 return (wx // wtotal, wy // wtotal) if wtotal else None @staticmethod def pos_after(current, move): x, y = current dx, dy = Grid.VECT[move] return x + dx, y + dy def get_move_to(self, p): return next(m for m in MOVES if grid.pos_after(grid.kirk, m) == p) @staticmethod def dist(p1, p2): xa, ya = p1 xb, yb = p2 return abs(xa - xb) + abs(ya - yb) def get_neighbors(self, x, y, diags=False): neighs = [(x, y - 1), (x - 1, y), (x + 1, y), (x, y + 1)] if diags: neighs += [(x - 1, y - 1), (x + 1, y - 1), (x - 1, y + 1), (x + 1, y + 1)] return [(x, y) for x, y in neighs if 0 <= x < self.w and 0 <= y < self.h] def line(self, x1, y1, x2, y2): # special case if (x1, y1) == (x2, y2): return [(x1, y1)] # diagonal symmetry vertically_oriented = (abs(y2 - y1) > abs(x2 - x1)) if vertically_oriented: y1, x1, y2, x2 = x1, y1, x2, y2 # horizontal symmetry reversed_sym = (x1 > x2) if reversed_sym: x2, y2, x1, y1 = x1, y1, x2, y2 # angle dx, dy = x2 - x1, y2 - y1 alpha = (abs(dy) / dx) offset = 0.0 step = 1 if dy > 0 else -1 result = [] y = y1 for x in range(x1, x2 + 1): if vertically_oriented: result.append((y, x)) else: result.append((x, y)) offset += alpha if offset > 0.5: y += step offset -= 1.0 if reversed_sym: result.reverse() return result def _get_quarters(self, x, y): return {(x - 1, y - 1): [(x - 1, y), (x - 1, y - 1), (x, y - 1)], (x + 1, y - 1): [(x, y - 1), (x + 1, y - 1), (x + 1, y)], (x + 1, y + 1): [(x + 1, y), (x + 1, y + 1), (x, y + 1)], (x - 1, y + 1): [(x, y + 1), (x - 1, y + 1), (x - 1, y)]} def update_corners(self): corners = set() for p, c in self.cells.items(): if c == Grid.WALL: for corner, quarter in self._get_quarters(*p).items(): if all(self.cells.get(n, Grid.WALL) != Grid.WALL for n in quarter): corners.add(corner) self.corners = list(corners) def way(self, start, target, known_only=False): nodes = Queue() origin = PathNode(*start) nodes.put(origin, 0) waypoints = set(self.corners) | {start, target} neighbors = {} passable = [Grid.EMPTY] if known_only else [Grid.EMPTY, Grid.UNKNOWN] for waypoint in waypoints: neighbors[waypoint] = [] for other in waypoints: if other is waypoint: continue sight = self.line(*other, *waypoint)[1:-1] if all(self.cells.get(p, "#") in passable for p in sight) and not any(w in sight for w in waypoints): neighbors[waypoint].append((other, Grid.dist(waypoint, other))) while nodes: current = nodes.get() if current == target: path = [] previous = current while previous: if previous != start: path.insert(0, previous) previous = previous.parent return path for n, dist in neighbors[current]: if n in current.ancestors(): continue cost = current.cost + dist priority = cost + Grid.dist(n, target) node = PathNode(*n, current) node.cost = cost nodes.put(node, priority) return None def path(self, start, target, known_only=False): nodes = Queue() origin = PathNode(*start) nodes.put(origin, 0) neighbors = [] its, break_on, broken = 0, 10000, False self.costs = {} for p, c in self.cells.items(): cost = 0 if c == Grid.WALL: cost = -1 elif known_only and c == Grid.UNKNOWN: cost = -1 else: cost = 2 if c == Grid.UNKNOWN else 1 self.costs[p] = cost while nodes: current = nodes.get() if current == target or broken: path = [] previous = current while previous: if previous != start: path.insert(0, previous) previous = previous.parent return path neighbors = self.neighbors[current] for x, y in neighbors: if (x, y) == current.parent: continue its += 1 if its > break_on: broken = True break if self.costs[(x, y)] < 0: continue cost = current.cost + self.costs[(x, y)] priority = cost + Grid.dist((x, y), target) node = PathNode(x, y, current) node.cost = cost nodes.put(node, priority) return None def optim_path(self, origin, target, known_only=False, first_steps=False): way = self.way(origin, target, known_only) if way: if first_steps: path = self.path(origin, way[0], known_only) else: way.insert(0, origin) path = sum([self.path(start, target, known_only) for start, target in zip(way, way[1:])], []) else: path = self.path(origin, target, known_only) return path def explore(self): if not self.to_explore is None: return self.to_explore buffer = [self.kirk] tested = set() while buffer: new_buffer = [] for p in buffer: for n in self.neighbors[p]: if n in tested: continue c = self.cells[n] if c == Grid.UNKNOWN: return n if c != Grid.WALL: new_buffer.append(n) tested.add(n) buffer = new_buffer return None grid = Grid(w, h) fuel = 1201 coming_back = False turn = 0 comeback_found = None while True: turn += 1 fuel -= 1 y, x = [int(i) for i in input().split()] grid.update((x, y), [list(input()) for j in range(grid.h)]) if grid.kirk == grid.control_room: coming_back = True log("Position:", grid.kirk, "CR:", grid.control_room) log("Fuel:", fuel, "Countdown:", countdown) path = [] if grid.control_room is None: log("> Looking for the control room") target = grid.explore() path = grid.optim_path(grid.kirk, target) next_move = grid.get_move_to(path[0]) elif not coming_back: log("> Have found the control room") if not comeback_found: comeback = grid.optim_path(grid.control_room, grid.start, True) else: comeback = comeback_found log("comeback's length: ", len(comeback) if comeback else None) log("comeback: ", comeback) if not comeback: log(" Path to start can not be computed") if fuel > 300: log(" Path to start can not be computed: explore") target = grid.explore() path = grid.optim_path(grid.kirk, target) next_move = grid.get_move_to(path[0]) else: log(" Path to start can not be computed: go to control room") path = grid.optim_path(grid.kirk, grid.control_room) next_move = grid.get_move_to(path[0]) elif len(comeback) > countdown: log(" Path to start is to long, keep exploring") target = grid.explore() path = grid.optim_path(grid.kirk, target) next_move = grid.get_move_to(path[0]) else: log("> Go to the control room") comeback_found = comeback path = grid.optim_path(grid.kirk, grid.control_room) next_move = grid.get_move_to(path[0]) else: log("> Come back to the ship") path = grid.optim_path(grid.kirk, grid.start, True, True) next_move = grid.get_move_to(path[0]) log("\n"+grid.graph(path)) print(next_move)