#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

extern const char *__progname;

#define MAXCOLOURS 10

typedef struct state STATE;
typedef struct cq CQ;
typedef struct cqe CQE;
typedef struct xy XY;

struct xy {
  int x;
  int y;
  } ;

struct cq {
  CQE *h;
  CQE **t;
  } ;

struct cqe {
  CQE *link;
  XY xy;
  } ;

struct state {
  STATE *up;
  STATE *kid;
  STATE *sib;
  unsigned char *cells;
#define CORNER (MAXCOLOURS) // code assumes CORNER==MAXCOLOURS
#define MARK (MAXCOLOURS+1)
  unsigned int npresent[MAXCOLOURS+1];
  unsigned int moves;
  int heapx;
  int ncp;
  int hv;
#define MOVEF 100
#define PRESF 100
#define CORNF 100
  int move;
  } ;

static int w;
static int h;
static int wh;

static STATE *start;
static STATE **heap;
static int heapa;
static int heapn;
#define H_L(x) (((x)*2)+1)
#define H_R(x) (((x)+1)*2)
#define H_U(x) (((x)-1)/2)
static int leastmoves;
static STATE *leaststate;

static STATE *new_state(void)
{
 STATE *s;

 s = malloc(sizeof(STATE));
 s->cells = malloc(wh);
 return(s);
}

static void read_puzzle(void)
{
 int n;
 int x;
 int y;
 int i;
 char c;

 n = -1;
 scanf("%dx%d:%n",&w,&h,&n);
 if (n < 0)
  { fprintf(stderr,"%s: can't scan size\n",__progname);
    exit(1);
  }
 wh = w * h;
 start = new_state();
 for (i=MAXCOLOURS;i>=0;i--) start->npresent[i] = 0;
 i = 0;
 for (y=h;y>0;y--)
  { for (x=w;x>0;x--)
     { c = getchar();
#if MAXCOLOURS != 10
#error "Puzzle read code disgarees with MAXCOLOURS"
#endif
       switch (c)
	{ case '0': c = 0; break;
	  case '1': c = 1; break;
	  case '2': c = 2; break;
	  case '3': c = 3; break;
	  case '4': c = 4; break;
	  case '5': c = 5; break;
	  case '6': c = 6; break;
	  case '7': c = 7; break;
	  case '8': c = 8; break;
	  case '9': c = 9; break;
	  default:
	     fprintf(stderr,"%s: bad puzzle char `%c'\n",__progname,c);
	     exit(1);
	     break;
	}
       start->cells[i++] = c;
       start->npresent[(int)c] ++;
     }
  }
}

static void cq_init(CQ *q)
{
 q->h = 0;
 q->t = &q->h;
}

static void ff_maybe(STATE *s, CQ *q, int x, int y, int col)
{
 CQE *e;
 int c;
 int i;

 i = x + (y * w);
 c = s->cells[i];
 if (c == col)
  { s->npresent[col] --;
    s->npresent[CORNER] ++;
  }
 else if (c != CORNER)
  { return;
  }
 s->cells[i] = MARK;
 e = malloc(sizeof(CQE));
 e->link = 0;
 e->xy.x = x;
 e->xy.y = y;
 *q->t = e;
 q->t = &e->link;
}

static XY ff_dequeue(CQ *q)
{
 CQE *t;
 XY r;

 t = q->h;
 q->h = t->link;
 if (! q->h) q->t = &q->h;
 r = t->xy;
 free(t);
 return(r);
}

static void floodfill(STATE *s, int col)
{
 CQ q;
 XY xy;
 int i;

 cq_init(&q);
 ff_maybe(s,&q,0,0,col);
 while (q.h)
  { xy = ff_dequeue(&q);
    if (xy.x > 0) ff_maybe(s,&q,xy.x-1,xy.y,col);
    if (xy.y > 0) ff_maybe(s,&q,xy.x,xy.y-1,col);
    if (xy.x < w-1) ff_maybe(s,&q,xy.x+1,xy.y,col);
    if (xy.y < h-1) ff_maybe(s,&q,xy.x,xy.y+1,col);
  }
 for (i=wh-1;i>=0;i--) if (s->cells[i] == MARK) s->cells[i] = CORNER;
}

static void set_hv(STATE *s)
{
 int i;
 int np;

 np = 0;
 for (i=MAXCOLOURS-1;i>=0;i--) if (s->npresent[i]) np ++;
 s->ncp = np;
 s->hv = (s->moves * MOVEF) + (np * PRESF) - (s->npresent[CORNER] * CORNF);
}

static void heaproom(int n)
{
 if (n > heapa)
  { heapa = n + 8;
    heap = realloc(heap,heapa*sizeof(STATE *));
  }
}

static void reheap_down(int x)
{
 STATE *e;
 int l;
 int r;
 int s;

 e = heap[x];
 while (1)
  { l = H_L(x);
    if (l >= heapn) break;
    r = H_R(x);
    if ((r >= heapn) || (e->hv <= heap[r]->hv))
     { if (e->hv <= heap[l]->hv)
	{ break;
	}
       else
	{ s = l;
	}
     }
    else
     { if (e->hv <= heap[l]->hv)
	{ s = r;
	}
       else
	{ s = (heap[l]->hv < heap[r]->hv) ? l : r;
	}
     }
    heap[x] = heap[s];
    heap[x]->heapx = x;
    x = s;
  }
 heap[x] = e;
 e->heapx = x;
}

static void reheap_up(int x)
{
 STATE *e;
 int u;

 e = heap[x];
 while (1)
  { if (x < 1) break;
    u = H_U(x);
    if (e->hv >= heap[u]->hv) break;
    heap[x] = heap[u];
    heap[x]->heapx = x;
    x = u;
  }
 heap[x] = e;
 e->heapx = x;
}

static void setup(void)
{
 floodfill(start,start->cells[0]);
 start->up = 0;
 start->kid = 0;
 start->sib = 0;
 start->moves = 0;
 heapa = 8;
 heap = malloc(heapa*sizeof(STATE *));
 heapn = 1;
 heap[0] = start;
 start->heapx = 0;
 set_hv(start);
 leastmoves = wh;
 leaststate = 0;
}

static STATE *state_copy(STATE *s)
{
 STATE *n;

 n = malloc(sizeof(STATE));
 *n = *s;
 n->cells = malloc(wh);
 bcopy(s->cells,n->cells,wh);
 return(n);
}

static void state_free(STATE *s)
{
 free(s->cells);
 free(s);
}

static void dump_cells(FILE *, const unsigned char *)
	__attribute__((__used__));
static void dump_cells(FILE *to, const unsigned char *cv)
{
 int i;

 for (i=0;i<wh;i++)
  { switch (cv[i])
     { case CORNER:
	  putc('*',to);
	  break;
       case MARK:
	  putc('?',to);
	  break;
       case 0 ... 9:
	  putc('0'+cv[i],to);
	  break;
       default:
	  abort();
	  break;
     }
  }
}

static void dump_history(FILE *to, STATE *s)
{
 if (s->up)
  { dump_history(to,s->up);
    printf("%d",s->move);
  }
}

static void search(void)
{
 STATE *s;
 STATE *n;
 int c;
 int ncorner;

 while (1)
  { if (heapn < 1) break;
    heapn --;
    s = heap[0];
    (void)((volatile STATE *)s)->up;
    if (heapn)
     { heap[0] = heap[heapn];
       reheap_down(0);
     }
    if (s->moves+s->ncp < leastmoves)
     { ncorner = s->npresent[CORNER];
       n = 0;
       for (c=MAXCOLOURS-1;c>=0;c--)
	{ if (! n) n = state_copy(s);
	  floodfill(n,c);
	  if (n->npresent[CORNER] == ncorner) continue;
	  n->moves ++;
	  n->kid = 0;
	  n->up = s;
	  n->sib = s->kid;
	  n->move = c;
	  s->kid = n;
	  set_hv(n);
	  if ((n->ncp == 0) && (n->moves < leastmoves))
	   { leastmoves = n->moves;
	     leaststate = n;
	     printf("New best\n");
	     printf("recording moves %d ncp %d hv %d via ",n->moves,n->ncp,n->hv);
	     dump_history(stdout,n);
	     putchar('\n');
	   }
	  heaproom(heapn+1);
	  heap[heapn++] = n;
	  reheap_up(heapn-1);
	  n = 0;
	}
       if (n) state_free(n);
     }
  }
}

int main(void)
{
 read_puzzle();
 setup();
 search();
 return(0);
}