#include <stdio.h>
#include <stdlib.h>
#define MAXCT 100000
#define LIMIT 10
int map[LIMIT][LIMIT];
int evals;

int getmap(int i, int j)
{
    if (i<0) return 0;
    if (j<0) return 0;
    if (i>=LIMIT) return 0;
    if (j>=LIMIT) return 0;
    return(map[i][j]);
}

int random_int(int n) // 0 以上 n - 1 以下の整数の乱数を返す
{
  return (int)((double)rand()/((double)RAND_MAX+1.0)*n);
}

main()
{
  int k,i,j;
  int success,ans,d1,d2;
  int mmax,seed;

  scanf("%d",&seed); // シードの入力
  printf("seed = %d\n",seed);
  srand(seed);       // 乱数の初期化
  // ランダムな地図の作成
  mmax = 0; // 最高地点の高さを保持する変数
  for (i=0;i<LIMIT;i++){
     for (j=0;j<LIMIT;j++){
       map[i][j]=random_int(LIMIT);
     printf("%3d ",map[i][j]);
     if (mmax<map[i][j]) mmax= map[i][j];
     }
     printf("\n");
  }
  evals = 0; // 評価回数のカウント
  success = 0; // 成功回数のカウント
  for (k=0;k<MAXCT;k++) {
          i = random_int(LIMIT); // 初期値点の生成
          j = random_int(LIMIT);
          ans=search_steepest_ascent(i,j);
          if (ans == mmax) success++; // 最高点が見つかった
   }
  printf("Search by steepest ascent --> %d / %d = %f\n",
         success, evals, (1.0*success)/evals);
}

int steepest_ascent(int i1, int j1, int *ip2, int *jp2)
{ // (i1,j1)の周りに高いとこがあるなら(*ip2,*jp2)にセット
  int temp,temp2,d1,d2;
  temp = getmap(i1,j1);
  for (d1=-1;d1<=1;d1++)
    for (d2=-1;d2<=1;d2++)
      if ((temp2=getmap(i1+d1,j1+d2))>temp){
        *ip2=i1+d1;
        *jp2=j1+d2;
        temp = temp2;
      }
  evals = evals + 8;
  if (temp==getmap(i1,j1)) return -1; // 高いとこがないなら-1を返す
  return (getmap(*ip2,*jp2));
}

int search_steepest_ascent(int i, int j)
{ // 局所探索の実行部分
  int i2,j2,temp;
  while (1) {
    temp = steepest_ascent(i,j,&i2,&j2);
    if (temp==-1) break;
    i=i2; j=j2;
  }
  return (getmap(i,j));
}