L'énoncé provient de la compétition Blue Bridge Cup, problème numéro 118, intitulé "Tour de Robots".

Le problème consiste à construire une structure pyramidale avec des robots de deux types ('a' et 'b') en respectant certaines règles de placement. L'approche utilisée est le parcours en profondeur (DFS) pour explorer toutes les configurations possibles.

Voici la solution finale optimisée :

#include <stdio.h>
#include <stdlib.h>
char grille[500][500] = {'\0'};
int resultat = 0;
int m, n;

int Valider(int niveau) {
    for (int j = 0; j <= niveau; j++) {
      if(grille[niveau - 1][j] == 'a') {
        if(grille[niveau][j] != grille[niveau][j + 1]) {
          return 0;
        }
      }
      if(grille[niveau - 1][j] == 'b') {
        if(grille[niveau][j] == grille[niveau][j + 1]) {
          return 0;
        }
      }
    }
  return 1;
}

void ParcoursProfondeur(int restantA, int restantB, int position, int niveau) {
  if(restantA == 0 && restantB == 0) {
    if(Valider(niveau)) {
      resultat++;
      return;
    }
  }
  if(niveau > 0 && position == (niveau + 1)) {
    if(!Valider(niveau)) {
      return;
    }
  }
  if(position == (niveau + 1)) {
    ParcoursProfondeur(restantA, restantB, 0, niveau + 1);
  } else {
    if(restantA > 0) {
      grille[niveau][position] = 'a';
      ParcoursProfondeur(restantA - 1, restantB, position + 1, niveau);
    }
    if(restantB > 0) {
      grille[niveau][position] = 'b';
      ParcoursProfondeur(restantA, restantB - 1, position + 1, niveau);
    }
  }
  
}

int main(int argc, char *argv[]) {
  scanf("%d %d", &m, &n);
  ParcoursProfondeur(m, n, 0, 0);
  printf("%d", resultat);
  return 0;
}

Voici une version précédente qui n'a pas passé tous les tests :

#include <stdio.h>
#include <stdlib.h>
char matrice[30][30] = {'\0'};
int reponse = 0;
int m, n;

int Verifier(int niveau) {
  for (int i = 0; i < niveau; i++) {
    for (int j = 0; j <= i; j++) {
      if(matrice[i][j] == 'a') {
        if(matrice[i + 1][j] != matrice[i + 1][j + 1]) {
          return 0;
        }
      }
      if(matrice[i][j] == 'b') {
        if(matrice[i + 1][j] == matrice[i + 1][j + 1]) {
          return 0;
        }
      }
    }
  }
  return 1;
}

void Explorer(int A, int B, int position, int niveau) {
  if(A == 0 && B == 0) {
    if(Verifier(niveau)) {
      reponse++;
    }
    return;
  }
  if(position == (niveau + 1)) {
    Explorer(A, B, 0, niveau + 1);
  } else {
    if(A > 0) {
      matrice[niveau][position] = 'a';
      Explorer(A - 1, B, position + 1, niveau);
    }
    if(B > 0) {
      matrice[niveau][position] = 'b';
      Explorer(A, B - 1, position + 1, niveau);
    }
  }
  
}

int main(int argc, char *argv[]) {
  scanf("%d %d", &m, &n);
  Explorer(m, n, 0, 0);
  printf("%d", reponse);
  return 0;
}

Optimisations réalisées

L'optimisation principale concerne la foncsion de validation. Dans la version initiale, la fonction vérifiait toute la structure pyramidale après chaque placement complet, ce qui était coûteux en temps de calcul.

Version originale de la validation

int Verifier(int niveau) {
  for (int i = 0; i < niveau; i++) {
    for (int j = 0; j <= i; j++) {
      if(matrice[i][j] == 'a') {
        if(matrice[i + 1][j] != matrice[i + 1][j + 1]) {
          return 0;
        }
      }
      if(matrice[i][j] == 'b') {
        if(matrice[i + 1][j] == matrice[i + 1][j + 1]) {
          return 0;
        }
      }
    }
  }
  return 1;
}

Version optimisée de la validation

int Valider(int niveau) {
    for (int j = 0; j <= niveau; j++) {
      if(grille[niveau - 1][j] == 'a') {
        if(grille[niveau][j] != grille[niveau][j + 1]) {
          return 0;
        }
      }
      if(grille[niveau - 1][j] == 'b') {
        if(grille[niveau][j] == grille[niveau][j + 1]) {
          return 0;
        }
      }
    }
  return 1;
}

Autre optimisation

La condition de terminaison a également été modifiée :

Version originale

if(A == 0 && B == 0) {
    if(Verifier(niveau)) {
      reponse++;
    }
    return;
  }

Vertion optimisée

if(A == 0 && B == 0) {
    if(Valider(niveau)) {
      resultat++;
      return;
    }
  }
  if(niveau > 0 && position == (niveau + 1)) {
    if(!Valider(niveau)) {
      return;
    }
  }

La principale amélioration consiste à passer d'une double boucle vérifiant toutes les lignes depuis le début, à une vérification uniquement entre la ligne actuelle et la précédente après chaque placement. Cela réduit considérablement la complexité temporelle de l'algorithme.