#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);
}

float temperature = 100.0;
float coolingRate = 0.8;
float Endtemperature = 0.1;

int flag; // flag==1なら焼きなまし法, flag==0なら山登り法

/* minとmaxの間の実数乱数を発生する関数 */
double random_float(double min, double max)
{
    return min + ((max-min)*rand())/RAND_MAX;
}

// test関数の定義
#define test(m,c,T) (exp((m-c)/T)>random_float(0.0,1.0))

int steepest_ascent(int i1, int j1, int *ip2, int *jp2)
{
  int temp,temp2,d1,d2;
  temperature *= coolingRate; // Step4: T:=rTの計算
  temp = getmap(i1,j1);
  for (d1=-1;d1<=1;d1++)
    for (d2=-1;d2<=1;d2++){
      evals++;
      if ((temp2=getmap(i1+d1,j1+d2))>temp ||
          (temp2 < temp && flag==1 && test(temp2,temp,temperature))){
        *ip2=i1+d1;
        *jp2=j1+d2;
        temp = temp2;
        if (flag == 1) return (getmap(*ip2,*jp2));
      }
    }
  if (temp==getmap(i1,j1)) return -1; // 局所解だった
  if ((flag == 1) && (temperature < Endtemperature)) 
    return -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));
}