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

#define N 10
#define P 0.5

int rand_bit(double p);
int **generate_random_grid(int n, float p);
int percolate(int **grid, int n);
void flow(int **grid, int n);
void flowrec(int **grid, int n, int i, int j);
void print_grid(int **grid, int n);
  
int main() {
  int **grid;

  srand(time(NULL));
  
  // création d'une grille aléatoire
  
  grid = generate_random_grid(N,P);

  // test de percolation de la grille
  
  printf("Percolate ? ");
  if (percolate(grid, N))
    printf("Yes\n");
  else
    printf("No\n");

  // affichage de la grille avec les cases marquées
  print_grid(grid,N);
  
  return 0;
}

int rand_bit(double p){
    if(p == 1.0){
        return 1;   
    }
    double r = ((double)rand())/((double)RAND_MAX);
    return r<p?1:0;
}

int **generate_random_grid(int n, float p) {
  int **grid = malloc(n * sizeof(int *));

  if (grid == NULL) {
    printf("Erreur d'allocation dans la fonction generate_random_grid\n");
    exit(-1);
  }
    
  for (int i = 0; i < n; i++) {
    grid[i] = malloc(n * sizeof(int));
    if (grid[i] == NULL) {
      printf("Erreur d'allocation dans la fonction generate_random_grid\n");
      exit(-1);
    }
    for (int j = 0; j < n; j++) {
      grid[i][j] = rand_bit(p);
    }
  }

  return grid;
}

int percolate(int **grid, int n) {
  flow(grid,n);   // fonction qui effectue le marquage des cases
  for (int j = 0; j < n; j++)
    if (grid[n-1][j] == 2)
      return 1;
  return 0;
}

void flow(int **grid, int n) {
  for (int j = 0; j < n; j++)
     flowrec(grid, n, 0, j);
}

void flowrec(int **grid, int n, int i, int j) {
  // Cas de base
  if (i < 0 || i >= n || j < 0 || j >= n) return;
  if (grid[i][j] == 1 || grid[i][j] == 2) return;
  // Cas inductif
  grid[i][j] = 2;
  flowrec(grid, n, i+1, j); // Bas
  flowrec(grid, n, i, j+1); // Droite
  flowrec(grid, n, i, j-1); // Gauche
  flowrec(grid, n, i-1, j); // Haut
}

void print_grid(int **grid, int n) {
  
  for (int i = 0; i < n; i++) {
    printf("|");
    for (int j = 0; j < n; j++) {
      switch(grid[i][j]) { 
      case 0: 
	printf(" ");
	break;
      case 1:
	printf("#");
	break;
      case 2:
	printf("o");
      }
    }    
    printf("|\n");
  }

}