- 追加された行はこの色です。
- 削除された行はこの色です。
[[問題文>練習問題#d4135691]]
import sys, heapq
#!/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.reachable = reachable
self.parent = None
self.g = 0
self.h = 0
self.f = 0
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.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 __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 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 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_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 __get_heuristic(self, cell):
return N * (abs(cell.r - self.end.r) + abs(cell.c - self.end.c))
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 __get_cell(self, r, c):
return self.cells[r * self.grid_height + c]
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()
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
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) ]
mp = list(map(list, mp))
astar = AStar(mp)
astar.init_grid()
astar.process()
