#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXCT 100000
#define LIMIT 100
int map[LIMIT][LIMIT];
double random_float(double, double);
float temperature = 100.0;
float coolingRate = 0.8;
float Input_temp;
float Input_cool;
float Endtemperature = 0.1;
int evals;
int flag=1;

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 seed;
  int mmax;
  printf("seed?\n");
  scanf("%d",&seed); /* シードの入力 */
  printf("seed = %d\n",seed);
  srand(seed);       /* 乱数の初期化 */
  printf("Anneling: temp cool\n");
  scanf("%f %f",&Input_temp, &Input_cool);
  printf("%f %f\n",Input_temp, Input_cool);
  temperature = Input_temp;
  coolingRate = Input_cool;
  if (temperature < 0.0) flag=0;
  if (flag==0) printf("This is just a local search\n");
     else printf("This is a simulated annealing search\n");
  for (i=0;i<LIMIT;i++)
     for (j=0;j<LIMIT;j++)
       map[i][j]=random_int(LIMIT*LIMIT);
  mmax = 0;
  for (i=0;i<LIMIT;i++)
     for (j=0;j<LIMIT;j++)
       if (mmax<map[i][j]) mmax= map[i][j];
  evals = 0;
  success = 0;
  for (k=0;k<MAXCT;k++) {
          i = random_int(LIMIT);
          j = random_int(LIMIT);
          temperature = Input_temp;
          coolingRate = Input_cool;
          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);
}

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

double random_float(double min, double max)
{
    return min + ((max-min)*rand())/RAND_MAX;
}