/* Counting the Paths on a Grid 
 * 2008-05-13: とりあえず書いてみたけど間違っているような気がする。
 */


#include <stdlib.h>
#include <stdio.h>

static char grids[11][11];

static double sum_length = 0;
static double sum_paths = 0;
static double sum_hitc = 0;
static long sum_num ;

void initrand()
{
  srand(0);
}

int getrand(int max) /* 0 < max <= 3 */
{
  int r;
  do { r = rand() & 3; } while (r > max);
  return r;
}


void clear_grids()
{
  int x, y;
  for (y = 0; y <= 10; y++){
    for (x = 0; x <= 10; x++){
      grids[x][y] = 0;
    }
  }
}

void calc_candidates(int x, int y,
		     int *num_cands, int *next_x, int *next_y)
{
  int right, up, left, down, r;

  right = 1;
  up    = 1;
  left  = 1;
  down  = 1;

  if (x == 0 || y == 0){
    left  = 0;
    down  = 0;
  } 

  if (x == 10){
    down  = 0;
    right = 0;
  }

  if (y == 10){
    up    = 0;
    left  = 0;
  }

  if (up    && grids[x][y+1]){ up    = 0; }
  if (down  && grids[x][y-1]){ down  = 0; }
  if (right && grids[x+1][y]){ right = 0; }
  if (left  && grids[x-1][y]){ left  = 0; }

  *num_cands = up + down + right + left;

  r = 0;
  if (*num_cands > 1){
    r = getrand(*num_cands - 1);
  }

  if ((r -= right) < 0){
    *next_x = x + 1;
    *next_y = y;
  } else if ((r -= up)    < 0){
    *next_x = x;
    *next_y = y + 1;
  } else if ((r -= left)  < 0){
    *next_x = x - 1;
    *next_y = y ;
  } else if ((r -= down)  < 0){
    *next_x = x;
    *next_y = y - 1;
  }
}

int generate_a_path()
{
  int x, y, n, next_x, next_y;
  int hitc;
  double npaths;
  int length;

  clear_grids();

  grids[0][0] = 1;
  x = 0;
  y = 0;

  npaths = 1;
  length = 0;

  hitc = 0;

  while (x != 10 || y != 10){
    if (x == 5 && y == 5){
      hitc = 1;
    }

    calc_candidates(x, y, &n, &next_x, &next_y);
    printf("(%d, %d), %d -> ", x, y, n);
    x = next_x;
    y = next_y;
    grids[x][y] = 1;

    if (n < 1){
      puts("faild.");
      return 0;
    }

    length++;
    npaths *= n;
  }

  printf("(10, 10): l = %d, n = %e\n", length, npaths);
  sum_num++;
  sum_length += length * npaths;
  sum_paths += npaths;

  if (hitc){
    sum_hitc += npaths;
  }

  return 1;
}

int
main(int argc, char** argv)
{
  int num, i;

  if (argc < 2 || (num = atol(argv[1])) < 1){
    num = 1;
  }

  initrand();

  i = 0;
  while (i < num){
    i += generate_a_path();
  }

  puts("----");
  printf("# of paths = %e, l = %.3f, hitc = %.3f\n", 
	 sum_paths / sum_num,
	 sum_length / sum_paths,
	 sum_hitc * 100 / sum_paths
	 );

  return 0;
}