#include <stdio.h>
#include <stdlib.h>
              
#define Side   (25)    /* matrix side */
#define Tree   'T'   
#define NoTree ' '              
#define Burn   '*'

int
  ran( int k ),
  get_density( void ),
  plant_forest( char forest[ ][ Side ], float density ),
  burning( char forest[ ][ Side ], int row, int col ),
  go_again( void );
void
  report( char forest[ ][ Side ], int density, int count ),
  print_border( void ),
  display( char forest[ ][ Side ], char msg[ ] ),
  percolate( char forest[ ][ Side ] );

main()
{
  char forest[ Side ][ Side ];
  int density, count;
  
  do {  
    /* Prompt for density percentage. */
    density = get_density();
    /* Initialize forest cells to Tree or NoTree. */ 
    count = plant_forest( forest, density); 
    /* Display forest in initial state. */
    display( forest, "Initial state" );
    /* Run simulation. */
    percolate( forest );
    /* Display forest in final state. */
    display( forest, "Final state" );
    /* Report statistics. */
    report( forest, density, count );
  } while ( go_again() );
  
  return EXIT_SUCCESS;
}

/* Return a random integer in the range 1..k. */
int ran( int k )
{
  double x = RAND_MAX + 1.0;
  return 1 + rand() * ( k / x );   
}   
  
/* Get tree density from user, in range 1..100. 
 * A density of 100 means that a tree occupies
 * a spot with a probability of 1.0. 
 */
int get_density( void )
{  
  int density;
  do { 
    printf( "\n\tDensity (range is 1 thru 100): " );
    scanf( "%d", &density );  
  } while ( density < 1 || density > 100 );
  return density;
}
        
/* Set forest cell to Tree or NoTree, depending on whether a randomly
 * generated integer equals or exceeds the density probability.
 */
int plant_forest( char forest[ ][ Side ], float density )
{
  int i, j; 
  int val; 
  int count = 0;
  for ( i = 0; i < Side; i++ )
    for ( j = 0; j < Side; j++ ) {
      val = ran( 100 ); 
      if ( val > density )
        forest[ i ][ j ] = NoTree;
      else {
        forest[ i ][ j ] = Tree;
        count++;
      }
    }
  return count;  /* count of trees in forest */
} 
  
/* Print report on forest before and after fire percolates.
 * Contrast requested with actual tree density.
 */
void report( char forest[ ][ Side ], int density, int count )
{             
  float actual = 
    ( ( float ) count / ( float ) ( Side * Side ) ) * 100.0; 
  int survivors = 0;
  int i, j;
  for ( i = 0; i < Side; i++ )
    for ( j = 0; j < Side; j++ )
      if ( Tree == forest[ i ][ j ] )
        survivors++;
  printf( "\n\t\tRequested density: %.1f", ( float ) density );
  printf( "\n\t\tActual density:    %.1f\n", actual ); 
  printf( "\n\t\tTrees at start:    %d", count );
  printf( "\n\t\tTrees at end:      %d\n", survivors );
}   

/* Display a horizontal border. */
void print_border( void )
{
  int i;         
  printf( "\n" );
  for ( i = 0; i < Side; i++ )
    printf( "+-" );
  printf( "+" );
}                  

/* Display forest. */
void display( char forest[ ][ Side ], char msg[ ] )
{
  int i, j;                                   
  
  printf( "\n\t\t%s\n", msg );
  print_border();
  
  for ( i = 0; i < Side; i++ ) {
    printf( "\n" );
    for ( j = 0; j < Side; j++ )
      printf( "|%c", forest[ i ][ j ] ); 
    printf( "|" ); 
    print_border();
  } 
  printf( "\n" );
} 
 
/* Determine whether a given tree's immediate neighbors in the
 * preceding row are burning. 
 */    
int burning( char forest[ ][ Side ], int row, int col )
{
  int left, right;
  left = ( col > 0 ) ? col - 1 : col;
  right = ( col < Side - 1 ) ? col + 1 : col;
  return Burn == forest[ row - 1 ][ left ] ||
         Burn == forest[ row - 1 ][ col ]    ||
         Burn == forest[ row - 1 ][ right ];  
}

void percolate( char forest[ ][ Side ] )
{        
  int i, j;
  
  /* Ignite first row of trees. */
  for ( j = 0; j < Side; j++ )
    if ( Tree == forest[ 0 ][ j ] )
      forest[ 0 ][ j ] = Burn;    
                              
  /* Percolate fire through remaining rows. */
  for ( i = 1; i < Side; i++ )                
    for ( j = 0; j < Side; j++ ) 
      if ( Tree == forest[ i ][ j ] &&
           burning( forest, i, j ) )
        forest[ i ][ j ] = Burn;
}
           
/* Check whether user wants to continue. */
int go_again( void )
{
  char ans[ 10 ];
  printf( "\n\n\t\tAgain? (y/n) " );
  scanf( "%s", ans );
  return 'Y' == ans[ 0 ] || 'y' == ans[ 0 ];
}