[[問題文>練習問題#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()


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS