#include <stdio.h>
/* worm_world_no3用 */
int x[100][100] = {
  {2,13,20,9,19,8,16,12},
  {22,15,16,14,14,11,12,5},
  {13,12,3,6,4,12,8,15},
  {4,21,8,18,17,13,5,1},
  {9,14,15,19,15,4,4,2},
  {16,6,16,4,11,16,3,17},
  {3,15,15,3,15,14,8,21},
  {22,19,16,24,0,19,8,22}
};
int i,j; /* スタート地点の座標 */
int len;      /* ある地点からスタートしたときのパスの長さ */
int path[25]; /* ある地点からスタートしたときのパス */
int max_from_i, max_from_j; /* 最長パスのスタート地点の座標 */
int max_len=0;              /* 最長パスの長さ */
int max_path[25];           /* 最長パス */
int min_from_i, min_from_j; /* 最短パスのスタート地点の座標 */
int min_len=25;             /* 最短パスの長さ */
int min_path[25];           /* 最短パス */

struct flags {
  int flg[4]; /* 次に進める(0)か，進めない(1)かのフラグ. flg[0]から順に上下左右 */
  int num;    /* 次に進める方向の数 */
};

void set_next_point(int icur, int jcur, int p[], int path_len) 
{
  struct flags next;
  int next_i, next_j; /* 次の地点の座標 */
  int next_p[25];
  int n;
  /* 初期化 */
  for (n=0; n<4; n++) next.flg[n]=0;
  next.num=0;
  /* 上下左右が壁の場合，フラグを1にセット */
  if (icur==0) next.flg[0]=1;
  if (icur==7) next.flg[1]=1;
  if (jcur==0) next.flg[2]=1;
  if (jcur==7) next.flg[3]=1;
  /* これまで通ってきたパスと同じ数の場合，フラグを1にセット */
  for (n=0; n<path_len; n++) {
    if ((icur>0) && (p[n]==x[icur-1][jcur])) next.flg[0]=1;
    if ((icur<7) && (p[n]==x[icur+1][jcur])) next.flg[1]=1;
    if ((jcur>0) && (p[n]==x[icur][jcur-1])) next.flg[2]=1;
    if ((jcur<7) && (p[n]==x[icur][jcur+1])) next.flg[3]=1;
  }
  /* 以上の調査から，次に進める方向の数をカウント */
  for (n=0; n<4; n++) {
    if (next.flg[n]==0) next.num++;
  }
  /* これ以上進むことが不可能なとき，記録を更新 */
  if ((next.num==0)&&(path_len > len)) {
    len=path_len;
    for (n=0; n<path_len; n++) path[n]=p[n];
  }
  /* まだ先に進めるなら */
  else {
    for (n=0; n<path_len; n++) next_p[n]=p[n];
    for (n=0; n<4; n++) {
      if (next.flg[n]==0) { /* 次の地点の座標を設定 */
        switch(n) {
        case 0:
          next_i=icur-1; next_j=jcur; break;
        case 1:
          next_i=icur+1; next_j=jcur; break;
        case 2:
          next_j=jcur-1; next_i=icur; break;
        case 3:
          next_j=jcur+1; next_i=icur; break;
        }
        next_p[path_len]=x[next_i][next_j];
        /* 再帰呼び出しを行う */
        set_next_point(next_i, next_j, next_p, path_len+1); 
      }
    }
  }
}

main() 
{
  int k;
  int p[25]; 
  for (i=0; i<8; i++) {
    for (j=0; j<8; j++) {
      /* 初期化 */
      p[0]=x[i][j];
      len=0;
      for (k=0; k<25; k++) path[k]=0;
      set_next_point(i, j, p, 1);
      /* これまでの最長記録を更新したなら */
      if (len > max_len) {
        max_from_i=i; max_from_j=j;
        max_len=len;
        for (k=0; k<len; k++) max_path[k]=path[k];
      }
      /* これまでの最短記録を更新したなら */
      if (len < min_len) {
        min_from_i=i; min_from_j=j;
        min_len=len;
        for (k=0; k<len; k++) min_path[k]=path[k];
      }
    }
  }
  /* 最長パスの表示 */
  printf("The longest path from (%d, %d). (length = %d)\n", 
            max_from_i, max_from_j, max_len);
  for (k=0; k<max_len; k++) printf("%d ",max_path[k]);
  printf(" \n\n");
  /* 最短パスの表示 */
  printf("The shortest path from (%d, %d). (length = %d)\n", 
            min_from_i, min_from_j, min_len);
  for (k=0; k<min_len; k++) printf("%d ",min_path[k]);
  printf(" \n");
}