#!/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()
初心者用:スタートからゴールへの経路を全て塗りつぶすアルゴリズムです。
# coding: utf-8 #例題の迷路をリスト型で入力しておきます。 maze = ['######## #','# #','# ###### #','# # # #','# #### # #', '# # #','######## #','## # #','# # # #','# ########'] print('\nこれは入力された迷路です。') for i in range(10): #入力した迷路を表示します。 print(maze[i]) print('\nこれは経路を全て+で塗りつぶしたものです。') for i in range(10): #経路をすべて+で塗りつぶします。 maze[i] = maze[i].replace(' ','+') print(maze[i]) def dig(mat,row,col): st = mat[row-1][col] + mat[row][col+1] + mat[row+1][col] + mat[row][col-1] cnt = st.count('#') + st.count(' ') if cnt >= 3: mat[row] = mat[row][:col] + ' ' + mat[row][col+1:] else: pass def ent_dig(): for i in range(1,9): for j in range(1,9): if maze[i][j] == '+': dig(maze,i,j) cnt = 0 while True: pre_maze = list(maze) ent_dig() if maze == pre_maze: print('\n経路検出の結果です。') for i in range(10): print(maze[i]) break else: cnt += 1 print('\n{0}回目の誤経路削除の結果です。'.format(cnt)) for i in range(10): print(maze[i])