[[問題文>練習問題#d4135691]] #!/usr/bin/python # -*- coding: utf-8 -*- import heapq R, C, N = 10, 10, 10 try: input = raw_input except NameError: pass class Cell(object): def __init__(self, r, c, reachable): self.r = r self.c = c self.is_reachable = reachable self.parent = None self.moving_cost = 0 # 移動コスト self.heuristic_cost = 0 # ヒューリスティックコスト self.score = 0 # スコア = 移動コスト + ヒューリスティックコスト def __lt__(self, other): return self.heuristic_cost < other.heuristic_cost class AStar(object): def __init__(self, _mp): self.op = [] heapq.heapify(self.op) self.cl = set() self.cells = [] self.grid_height = R self.grid_width = C self.start = None self.end = None self.mp = _mp def init_grid(self): for r in range(self.grid_height): for c in range(self.grid_width): reachable = mp[r][c] != '#' self.cells.append(Cell(r, c, reachable)) for r in range(self.grid_height): for c in range(self.grid_width): if r == 0 and mp[r][c] == ' ': self.start = self.__get_cell(r, c) if r == R - 1 and mp[r][c] == ' ': self.end = self.__get_cell(r, c) def __get_heuristic(self, cell): return N * (abs(cell.r - self.end.r) + abs(cell.c - self.end.c)) def __get_cell(self, r, c): return self.cells[r * self.grid_height + c] def __get_adjacent_cells(self, cell): cells = [] if cell.r < self.grid_height - 1: cells.append(self.__get_cell(cell.r + 1, cell.c)) if cell.c < self.grid_width - 1: cells.append(self.__get_cell(cell.r, cell.c + 1)) if cell.r > 0: cells.append(self.__get_cell(cell.r - 1, cell.c)) if cell.c > 0: cells.append(self.__get_cell(cell.r, cell.c - 1)) return cells def __display_path(self): cell = self.end mp[self.start.r][self.start.c], mp[self.end.r][self.end.c] = '+', '+' while cell.parent is not self.start: cell = cell.parent mp[cell.r][cell.c] = '+' print('\n'.join(''.join(mp[r]) for r in range(R))) def __update_cell(self, adj, cell): adj.moving_cost = cell.moving_cost + N adj.heuristic_cost = self.__get_heuristic(adj) adj.parent = cell adj.score = adj.heuristic_cost + adj.moving_cost def process(self): heapq.heappush(self.op, (self.start.score, self.start)) while len(self.op): _, cell = heapq.heappop(self.op) self.cl.add(cell) if cell is self.end: self.__display_path() break adj_cells = self.__get_adjacent_cells(cell) for c in adj_cells: if c.is_reachable and c not in self.cl: if (c.score, c) in self.op: if c.moving_cost > cell.moving_cost + N: self.__update_cell(c, cell) else: self.__update_cell(c, cell) heapq.heappush(self.op, (c.score, c)) mp = [] while 1: try: mp.append(input()) except EOFError: break mp = list(map(list, mp)) astar = AStar(mp) astar.init_grid() astar.process()