Analysons les cas possibles en fonction du nombre de cellules vides. Une approche récursive avec mémoïsation permet d'optimiser la recherche. Nous traitons séparément les scénarios avec 1, 2 ou 3 cellules vides, ainsi que le cas où toutes les cellules sont vides.

Implémentation

### 2.1 : Fonction de vérification Pour comparer l'état actuel à l'état cible, implémentons une fonction booléenne :

bool verifier(int x1, int y1, int x2, int y2) {
    if (x1 != b[1][1] || y1 != b[1][2] ||
        x2 != b[2][1] || y2 != b[2][2]) {
        return false;
    }
    return true;
}

Cette fonction retuorne vrai uniquement si tous les éléments correspondent exactement à l'état cible. Dans la fonction récursive, intégrons cette vérificasion :

if (verifier(x1, y1, x2, y2)) {
    printf("Oui\n");
    exit(0);
}

### 2.2 : Cas d'une seule cellule vide Définissons un compteur 'vide' pour suivre le nombre de cellules vides. Pour chaque position vide, nous explorons les deux possibilités de déplacement :

if (vide == 1) {
    // Gestion des positions vides selon leur coordonnée
    if (y1 == 0) {
        if (!memo[0][x1][x2][y2]) {
            memo[0][x1][x2][y2] = 1;
            dfs(0, x1, x2, y2);
        }
        if (!memo[x1][y2][x2][0]) {
            memo[x1][y2][x2][0] = 1;
            dfs(x1, y2, x2, 0);
        }
        return;
    }
    // ... autres conditions similaires ...
}

La mémoïsation évite les calculs redondants en stockant les états déjà explorés. ### 2.3 : Cas de quatre cellules vides Pour le cas particulier de quatre cellules vides, ajoutons une condition spécifique :

if (vide == 4) {
    if (!memo[0][0][0][0]) {
        memo[0][0][0][0] = 1;
        dfs(0, 0, 0, 0);
    }
    return;
}

### 2.4 : Cas sans cellules vides Lorsque toutes les cellules sont pleines, la vérification s'effectue automatiquement avant l'appel récursif. Si l'état n'est pas valide, la fonction retourne directement.

### 2.5 : Fonction principale Initialisons les tableaux d'état initial et cible :

int a[3][3], b[3][3];
int vide = 0;

for (int i=1; i<=2; i++) {
    for (int j=1; j<=2; j++) {
        a[i][j] = lire();
        if (a[i][j] == 0) vide++;
    }
}

for (int i=1; i<=2; i++) {
    for (int j=1; j<=2; j++) {
        b[i][j] = lire();
    }
}

dfs(a[1][1], a[1][2], a[2][1], a[2][2]);
printf("Non\n");

Le programme affiche "Oui" si un chemin est trouvé, sinon "Non".