#include <stdio.h>
#define MAXN 200		/* Maximální velikost bludiště */
#define DELKA (MAXN*MAXN)	/* Maximální délka fronty */
struct pozice {
    int x, y;
};

 /* Fronty jsou kruhové buffery pevné velikosti. */
struct fronta {
    int zacatek, konec;
    struct pozice pozice[DELKA];
} mistnosti, dvere;

int matice[MAXN][MAXN];	       /* bludiště uložené takto: */
#define MISTNOST 0
#define ZED 1
#define DVERE 2
#define POKLAD 3
#define VCHOD 4
#define ZPRACOVANO 5
int velikost = 0;	       /* hrana bludiště */

struct pozice kam[MAXN][MAXN]; /* kudy z daného políčka vede nejkratší 
                                   cesta k pokladu */
int vzdal[MAXN][MAXN];	       /* vzdálenost jednotlivých políček */
int dalsikop;		       /* index prvních dveří, na které je třeba
                                   o kop více */

 /* Přidání políčka do fronty */
void pridej(struct fronta *f, int x, int y)
{
  f->pozice[f->konec].x = x;
  f->pozice[f->konec].y = y;
  f->konec = (f->konec + 1) % DELKA;
}

 /* Vyzvedne políčko z fronty. Vrací 0, pokud je fronta prázdná */
int vyzvedni(struct fronta *f, int *x, int *y)
{
  if (f->konec == f->zacatek)
    return 0;
  *x = f->pozice[f->zacatek].x;
  *y = f->pozice[f->zacatek].y;
  f->zacatek = (f->zacatek + 1) % DELKA;
  return 1;
}

 /* Vrátí vzdálenost prvmího políčka ve frontě */
int vzdalenost(struct fronta *f)
{
  if (f->zacatek == f->konec)	/* Je fronta prázdná? */
    return -1;		/* Vrátíme neexistující vzdálenost... */
  return vzdal[f->pozice[f->zacatek].x][f->pozice[f->zacatek].y];
}

 /* Vypíše nejkratší cestu */
void vypis(int x, int y)
{
  printf("Nejsnadneji ziskas poklad takto:\n");
  while (x >= 0) {
    int x1;
    printf("%d %d\n", x, y);
    x1 = x;
    x = kam[x][y].x;
    y = kam[x1][y].y;
  }
}
 /* Přidá dané políčko spolu se stejně vzdálenými dveřmi do fronty */
void pridej_mistnost(int x, int y)
{
  int dx, dy;
  pridej(&mistnosti, x, y);
  /* Je teď průchod dveřmi stejně výhodný jako momentální pozice? */
  while (vzdalenost(&dvere) == vzdal[x][y] && dalsikop > dvere.zacatek)
  {
    /* Zařadíme dveře do fronty k provedení */
    vyzvedni(&dvere, &dx, &dy);
    pridej(&mistnosti, dx, dy);
  }
}

 /* Zpracuje políčko - porozhlédne se po sousedech.
   Vrací 1, pokud cesta byla nalezena.
 */
int zpracuj(int x, int y)
{
  int x1, y1;

  for (x1 = x - 1; x1 <= x + 1; x1++)
    for (y1 = y - 1; y1 <= y + 1; y1++)
      if (((x1 != x) ^ (y1 != y)) &&
      /* tato podmínka zajistí, že se nebudu zabývat políčky, která sousedí
         pouze vrcholem. Pozn. \^ znamená bitový xor */
        x1 >= 0 && y1 >= 0 && x1 < velikost && y1 < velikost &&
        matice[x1][y1] != ZPRACOVANO && matice[x1][y1] != ZED)
      {
        kam[x1][y1].x = x;
        kam[x1][y1].y = y;
        if (matice[x1][y1] == VCHOD) {	/* Jsme v cíli? */
          vypis(x1, y1);
          return 1;
        }
        matice[x1][y1] = ZPRACOVANO;
        vzdal[x1][y1] = vzdal[x][y] + 1;
        /* Zařadíme sousední políčko do příslušné fronty */
        if (matice[x1][y1] == DVERE)
          pridej(&dvere, x1, y1);
        else
          pridej_mistnost(x1, y1);
      }
  return 0;
}
 /* načtení matice */
void cti()
{
  int i, j;

  scanf("%d", &velikost);
  getchar();		/* Načteme konec řádky, který nenačetl scanf()... */
  for (i = 0; i < velikost; i++)
  {
    for (j = 0; j < velikost; j++)
      matice[j][i] = getchar() - '0';
    getchar();		/* Načteme |\n| */
  }
}
int main(void)
{
  int x, y;

  cti();
  /* Poklad je třeba zařadit do fronty, aby se algoritmus rozjel. Musím
     jej přidat jako dveře, protože algoritmus začíná "dveřní" vlnou */
  for (x = 0; x < velikost; x++)
    for (y = 0; y < velikost; y++)
      if (matice[x][y] == POKLAD) {
        pridej(&dvere, x, y);
        matice[x][y] = ZPRACOVANO;
        kam[x][y].x = -1;
      }

  while (1) {
    if (vyzvedni(&dvere, &x, &y))	/* Vybere další dveře - jsou ještě? */
    {
      /* Přecházíme do oblasti, na kterou je třeba další kop? */
      if (dvere.zacatek > dalsikop)	
        dalsikop = dvere.konec;
      pridej_mistnost(x, y);	/* Přidáme všechny stejně vzdálené dveře */
    }
    else
      break;

    /* Projdeme celou oblast... */
    while (vyzvedni(&mistnosti, &x, &y))
      if (zpracuj(x, y))
        return 0;
  }
  printf("Cesta neexistuje. Smula, penize nebudou.\n");
  return 0;
}