# -*- coding: utf-8 -*-
import pdb
import sys
import heapq

class PriorityQueue:
    """
      Implements a priority queue data structure. Each inserted item
      has a priority associated with it and the client is usually interested
      in quick retrieval of the lowest-priority item in the queue. This
      data structure allows O(1) access to the lowest-priority item.

      Note that this PriorityQueue does not allow you to change the priority
      of an item.  However, you may insert the same item multiple times with
      different priorities.

      Copyright: 
        John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
        For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html      
    """
    def  __init__(self):
        self.heap = []

    def push(self, item, priority):
        pair = (priority,item)
        heapq.heappush(self.heap,pair)

    def pop(self):
        (priority,item) = heapq.heappop(self.heap)
        return item

    def isEmpty(self):
        return len(self.heap) == 0


def isGoal(grid):
    """
    On a atteint le  but si on a autant de  valeurs différentes que de
    cellules dans la grille.
    """
    values = set()
    for v in grid:
        values.add( v )
    if len(values) < len(grid):
        return False
    return True


def jumpTo(pos, grid, size):
    """
    Retourne un  couple formé  de "pos"  et d'une  copie de  la grille
    modifiée par le saut à la position "pos".
    """
    g = grid[:]
    x, y = pos
    idx = y * size + x
    dec = 0
    if x > 0:
        g[idx - 1] += 1
        dec += 1
    if y > 0:
        g[idx - size] += 1
        dec += 1
    if x < size - 1:
        g[idx + 1] += 1
        dec += 1
    if y < size - 1:
        g[idx + size] += 1
        dec += 1
    g[idx] -= dec
    return g
    
    
def solve(size=3, initialValue=5):
    # les valeurs minimales pour pouvoir donner à ses voisins.
    minimals = [4]*( size * size )
    idx = 0
    for y in range(size):
        for x in range(size):
            if x == 0:
                minimals[idx] -= 1
            if y == 0:
                minimals[idx] -= 1
            if x >= size - 1:
                minimals[idx] -= 1
            if y >= size - 1:
                minimals[idx] -= 1
            idx += 1
    # La grille iniale avec les valeurs de ces cellules.
    pos = (0,0)
    grid = jumpTo( pos, [initialValue]*( size * size ), size )
    fringe = PriorityQueue()
    fringe.push( (pos, grid, []), 0 )
    closedSet = set()
    count = 0
    while not fringe.isEmpty():
        pos, grid, steps = fringe.pop()
        count += 1
        if isGoal(grid):
            steps.append(pos)
            return (pos, grid, steps, count)
        x, y = pos
        key = ",".join([str(item) for item in grid]) + ";" + str(x) + "," + str(y)
        if key in closedSet:
            continue
        closedSet.add(key)
        steps.append( pos )
        idx = y * size + x
        if x > 0 and grid[idx - 1] >= minimals[idx - 1]:
            pos2 = (x - 1, y)
            grid2 = jumpTo( pos2, grid, size )
            steps2 = steps[:]
            g = len(steps2)
            h = 0
            f = g + h
            fringe.push( (pos2, grid2, steps2), f )
        if y > 0 and grid[idx - size] >= minimals[idx - size]:
            pos2 = (x, y - 1)
            grid2 = jumpTo( pos2, grid, size )
            steps2 = steps[:]
            g = len(steps2)
            h = 0
            f = g + h
            fringe.push( (pos2, grid2, steps2), f )
        if x < size - 1 and grid[idx + 1] >= minimals[idx + 1]:
            pos2 = (x + 1, y)
            grid2 = jumpTo( pos2, grid, size )
            steps2 = steps[:]
            g = len(steps2)
            h = 0
            f = g + h
            fringe.push( (pos2, grid2, steps2), f )
        if y < size - 1 and grid[idx + size] >= minimals[idx + size]:
            pos2 = (x, y + 1)
            grid2 = jumpTo( pos2, grid, size )
            steps2 = steps[:]
            g = len(steps2)
            h = 0
            f = g + h
            fringe.push( (pos2, grid2, steps2), f )