Problème des interrupteurs mystères : https://www.acwing.com/problem/content/97/

Lorsque les opérations de la première ligne sont déterminées, chaque opération suivante devient contrainte. Nous devons énumérer chaque état possible de la première ligne, en appuyant sur chaque interrupteur, qu'il soit allumé ou étient, pour trouver toutes les solutions possibles. Ensuite, nous parcourons chaque solution à partir de la première ligne.

Configuraton de la première ligne (ici, 1 indique que l'interrupteur est pressé, 0 qu'il ne l'est pas), ceci sert uniquement à afficher l'état après avoir pressé les interrupteurs de la première ligne.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5;
char grille[N][N], sauvegarde[N][N];
int deplacements[5] = {-1, 0, 1, 0, 0}, decalages[5] = {0, 1, 0, -1, 0};

void inverser(int x, int y)
{
    for (int i = 0; i < 5; i++)
    {
        int a = x + deplacements[i], b = y + decalages[i];
        if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        grille[a][b] = (grille[a][b] == '1') ? '0' : '1';
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        for (int i = 0; i < 5; i++) cin >> grille[i];

        int resultat = 10;
        for (int operation = 0; operation < 32; operation++)
        {
            memcpy(sauvegarde, grille, sizeof grille);
            int etapes = 0;
            for (int i = 0; i < 5; i++)
                if (operation >> i & 1)
                {
                    etapes++;
                    inverser(0, i);
                }

            for (int i = 0; i < 4; i++)
                for (int j = 0; j < 5; j++)
                    if (grille[i][j] == '0')
                    {
                        etapes++;
                        inverser(i + 1, j);
                    }

            bool eteint = false;
            for (int i = 0; i < 5; i++)
                if (grille[4][i] == '0')
                {
                    eteint = true;
                    break;
                }

            if (!eteint) resultat = min(resultat, etapes);
            memcpy(grille, sauvegarde, sizeof grille);
        }

        if (resultat > 6) resultat = -1;

        cout << resultat << endl;
    }

    return 0;
}

Frères pilotes (la solution optimale pour les problèmes 01 consiste à appuyer sur chaque poignée une seule fois) : https://www.acwing.com/problem/content/118/

Compression d'état + parcours en profondeur (DFS) Modification d'une grille 4x4 où chaque modification affecte la ligne et la colonne correspondantes

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 5;

char grille[N][N], sauvegarde[N][N];

int obtenirCoordonnees(int x, int y)
{
    return x * 4 + y;
}

void inverserCase(int x, int y)
{
    if (grille[x][y] == '+') grille[x][y] = '-';
    else grille[x][y] = '+';
}

void inverserLigneColonne(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        inverserCase(x, i);
        inverserCase(i, y);
    }

    inverserCase(x, y);
}

int main()
{
    for (int i = 0; i < 4; i++) cin >> grille[i];

    vector<PII> solution;
    for (int operation = 0; operation < 1 << 16; operation++)
    {
        vector<PII> temporaire;
        memcpy(sauvegarde, grille, sizeof grille);

        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (operation >> obtenirCoordonnees(i, j) & 1)
                {
                    temporaire.push_back({i, j});
                    inverserLigneColonne(i, j);
                }

        bool resteEteint = false;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (grille[i][j] == '+')
                    resteEteint = true;

        if (!resteEteint)
        {
            if (solution.empty() || solution.size() > temporaire.size()) solution = temporaire;
        }

        memcpy(grille, sauvegarde, sizeof grille);
    }

    cout << solution.size() << endl;
    for (auto op : solution) cout << op.x + 1 << ' ' << op.y + 1 << endl;

    return 0;
}

Retournement de pièces

On peut inverser les deux côtés, il suffit donc de commencer par la première pièce et d'inverser vers la droite jusqu'à l'avant-dernière pièce.

void inverser(int i){
    if(pieces[i]=='*') pieces[i]='o';
    else pieces[i]='*';
}
int main()
{
    cin >> pieces>> cible;
    int res=0;
    for (int i = 0; i+1 < pieces.size(); i ++ ){
        if(pieces[i]!=cible[i]){
            inverser(i),inverser(i+1);res++;
        }
    }
    cout << res;
    return 0;
}