#!/usr/bin/python

import heapq

class Cell(object):
    def __init__(self, x, y, is_wall):
        self.reachable = not is_wall
        self.x = x
        self.y = y
        self.parent = None
        # G, H, F are current costs
        self.g = 0 # cost to get to end pos
        self.h = 0 # cost to get to from start pos
        self.f = 0 # g + h

class AStar(object):
    def __init__(self, maze):
        # Open cells to still visit
        self.opened = []
        heapq.heapify(self.opened)

        # Visited cells list
        self.closed = set()

        # Initialize all cells
        self.init_grid()

    def init_grid(self):
        # Create cells by looping through the input maze
        for x in range(self.grid_width):
            for y in range(self.grid_height):
                if self.maze[y][x] == 1:
                    is_wall = True
                else:
                    is_wall  = False
                self.cells.append(Cell(x, y, is_wall))

    def solve(self):
        # Add starting cell to open heap queue
        heapq.heappush(self.opened, (self.start.f, self.start))
        while len(self.opened):
            # Pop cell from heap queue
            f, cell = heapq.heappop(self.opened)

            # Add cell to closed list so we don't process it twice
            self.closed.add(cell)

            # If ending cell, return found path
            if cell is self.end:
                return self.get_path()

            # Get adjacent cells for the current cell
            adj_cells = self.get_adjacent_cells(cell)
            for adj_cell in adj_cells:
                # If the adj_cell is not a wall and hasn't been visited
                if adj_cell.reachable and adj_cell not in self.closed:
                    # If adj_cell in open list from another cell, check if current path is
                    # better than the one previously found for this cell
                    if (adj_cell.f, adj_cell) in self.opened:
                        if adj_cell.g > cell.g + 10:
                            # If so, update its cost and parent with the current cell
                            self.update_cell(adj_cell, cell)
                    else:
                        # If adj_cell has never been visited before, update it with its
                        # cost and parent cell. Add to heap for use
                        self.update_cell(adj_cell, cell)
                        heapq.heappush(self.opened, (adj_cell.f, adj_cell))

def answer(maze):
    astar = AStar(maze)
    return astar.solve()

maze = [[0, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 1, 1, 1, 1, 1],
        [0, 1, 1, 1, 1, 1],
        [0, 0, 0, 0, 0, 0]]

print answer(maze)