import heapq

class Cell(object):

    def __init__(self, x, y, reachable):

        self.reachable = reachable

        self.x = x

        self.y = y

        self.parent = None

        self.g =

        self.h =

        self.f = 

class AStar(object):

    def __init__(self):

        self.op = []

        heapq.heapify(self.op)

        self.cl = set()

        self.cells = []

        self.gridHeight =

        self.gridWidth = 

    def init_grid(self):

        walls = ((, ), (, ), (, ), (, ), (, ),

                 (, ), (, ), (, ), (, ), (, ), (, ))

        for x in range(self.gridWidth):

            for y in range(self.gridHeight):

                if (x, y) in walls:

                    reachable = False

                else:

                    reachable = True

                self.cells.append(Cell(x, y, reachable))

        self.start = self.get_cell(, )

        self.end = self.get_cell(, )

    def get_heuristic(self, cell):

        return  * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))

    def get_cell(self, x, y):

        return self.cells[x * self.gridHeight + y]

    def get_adjacent_cells(self, cell):

        cells = []

        if cell.x < self.gridWidth-:

            cells.append(self.get_cell(cell.x+, cell.y))

        if cell.y > :

            cells.append(self.get_cell(cell.x, cell.y-))

        if cell.x > :

            cells.append(self.get_cell(cell.x-, cell.y))

        if cell.y < self.gridHeight-:

            cells.append(self.get_cell(cell.x, cell.y+))

        return cells

    def display_path(self):

        cell = self.end

        while cell.parent is not self.start:

            cell = cell.parent

            print 'path: cell: %d,%d' % (cell.x, cell.y)

    def update_cell(self, adj, cell):

        adj.g = cell.g +

        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:

                    if c in self.cl:

                        if (c.f, c) in self.op:

                            if c.g > cell.g + :

                                self.update_cell(c, cell)

                    else:

                        self.update_cell(c, cell)

                        heapq.heappush(self.op, (c.f, c))

if __name__ == "__main__":

    a = AStar()

    a.init_grid()

    a.process()