[[問題文>練習問題#d4135691]] import sys, heapq R, C, N = 10, 10, 10 class Cell(object): def __init__(self, r, c, reachable): self.r = r self.c = c self.reachable = reachable self.parent = None self.g = 0 self.h = 0 self.f = 0 class AStar(object): def __init__(self, mp): self.op = [] heapq.heapify(self.op) self.cl = set() self.cells = [] self.gridHeight = R self.gridWidth = C self.start = None self.end = None self.mp = mp def init_grid(self): for r in xrange(self.gridHeight): for c in xrange(self.gridWidth): reachable = False if mp[r][c] == '#' else True self.cells.append(Cell(r, c, reachable)) for r in xrange(self.gridHeight): for c in xrange(self.gridWidth): 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.gridHeight + c] def get_adjacent_cells(self, cell): cells = [] if cell.r < self.gridHeight - 1: cells.append(self.get_cell(cell.r+1, cell.c)) if cell.c < self.gridWidth - 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 xrange(R)) def update_cell(self, adj, cell): adj.g = cell.g + N adj.h = self.get_heuristic(adj) adj.parent = cell adj.f = adj.h + adj.g def process(self): heapq.heappush(self.op, (self.start.f, self.start)) while len(self.op): f, 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.reachable and c not in self.cl: if (c.f, c) in self.op: if c.g > cell.g + N: self.update_cell(c, cell) else: self.update_cell(c, cell) heapq.heappush(self.op, (c.f, c)) mp = [ list(sys.stdin.readline().strip()) for _ in xrange(R) ] astar = AStar(mp) astar.init_grid() astar.process()