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

void affiche(int mat[], int n, int m){
  for (int i = 0; i < n; i = i + 1){
    for (int j = 0; j < m; j = j + 1)
      printf("%5d", mat[i * m + j]);
    printf("\n");
  }
}

void affiche_chemin(bool chemin[], int n, int m){
  for (int i = 0; i < n; i = i + 1){
    for (int j = 0; j < m; j = j + 1)
      if (chemin[i * m + j])
        printf("\033[31;01m\u2588\u2588\033[00m");
      else printf("\u2588\u2588");
    printf("\n");
  }
}

int min(int a, int b){
  if (a <= b) return a;
  return b;
}

int *couts(int mat[], int n, int m){
  // Allocation
  int *couts = malloc(n * m * sizeof(int));
  // Cas de base
  couts[0 * m + 0] = mat[0 * m + 0];
  for (int i = 1; i < n; i = i + 1)
    couts[i * m + 0] =
      couts[(i-1) * m + 0] + mat[i * m + 0];
  for (int j = 1; j < m; j = j + 1)
    couts[0 * m + j] =
      couts[0 * m + (j-1)] + mat[0 * m + j];
  // Récurrence
  for (int i = 1; i < n; i = i + 1)
    for (int j = 1; j < m; j = j + 1)
      couts[i * m + j] =
        mat[i * m + j]
        + min(couts[(i-1) * m + j],
              couts[i * m + (j-1)]);
  return couts;
}

bool *chemin(int c[], int n, int m){
  bool *chemin = malloc(n * m * sizeof(bool));
  for (int i = 0; i < n * m; i = i + 1)
    chemin[i] = false;
  int pos = n * m - 1;
  while (pos != 0){
    chemin[pos] = true;
    int i = pos / m;
    int j = pos % m;
    // Sur un bord
    if (i == 0)      pos = pos - 1;
    else if (j == 0) pos = pos - m;
    // Cas général
    else if (c[pos - m] < c[pos - 1])
      pos = pos - m;
    else pos = pos - 1;
  }
  chemin[0] = true;
  return chemin;
}


int main(int argc, char *argv[]){
  srand(time(NULL));
  int exemple[800];
  for (int i = 0; i < 800; i = i + 1)
    exemple[i] = rand() % 1000;
  affiche(exemple, 40, 20);
  printf("\n");
  int *c = couts(exemple, 40, 20);

  affiche(c, 40, 20);
  printf("\n");
  bool *chem = chemin(c, 40, 20);

  affiche_chemin(chem, 40, 20);

  return 0;
}