Programme C++ pour vérifier si deux piles de lettres peuvent être effacées

Supposons qu'il y ait 2n lettres, chaque lettre porte un entier compris entre 1 et n. Il y a deux lettres avec le même numéro écrit dessus. Ces lettres sont divisées en m piles, et il y a une pile [i] lettre sur la i-ième pile. Notre tâche est de vider toutes les piles de la manière suivante :

• Nous devons sélectionner deux piles quelconques et supprimer les lettres du haut des deux piles.

• Les lettres que nous supprimons doivent avoir le même numéro.

Si nous pouvons effacer le tas m de cette manière, imprimez vrai, sinon renvoyez faux.

Donc, si l'entrée est n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}, alors la sortie sera vraie.

Il y a deux piles et les chiffres 2, 1 et 3 sont écrits sur les lettres de chaque pile. Ainsi, nous pouvons supprimer les lettres des deux piles et les vider de la manière indiquée.

Pour résoudre ce problème, nous suivrons les étapes suivantes :

Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
   k := size of stacks[i]
   for initialize j := 0, when j < k, update (increase j by 1), do:
      if j < 0, then:
         insert p at the end of dp[stacks[i, j]]
         (increase tvec[p] by 1)
      p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
   Define one queue q
   insert i into q
   while (q is not empty), do:
    if not tp[first element of q] and tvec[first element of q] is same as 0, then:
         for each element next in dp[first element of q], do:
             (decrease tvec[next] by 1)
             insert next into q
         tp[first element of q] := true
   delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
   if tvec[i] is not equal to 0, then:
return false
return true

Exemple

Voyons l'implémentation suivante pour une meilleure compréhension -

#include <bits/stdc++.h>
using namespace std;

bool solve(int n, int m, vector<vector<int>> stacks){
   vector<vector<int>> dp(n + 1);
   vector<int> tvec(n + 1);
   for(int i = 0; i < m; i++){
      int k = stacks[i].size();
      int p;
      for(int j = 0; j < k; j++){
         if(j > 0){
            dp[stacks[i][j]].push_back(p);
            tvec[p]++;
         }
         p = stacks[i][j];
      }
   }
   vector<bool> tp(n + 1);
   for(int i = 1; i <= n; i++){
      queue<int> q;
      q.push(i);
      while(!q.empty()){
         if(!tp[q.front()] && tvec[q.front()] == 0){
            for(auto next: dp[q.front()]){
               tvec[next]--;
               q.push(next);
            }
            tp[q.front()]=true;
         }
         q.pop();
      }
   }
   for(int i = 1; i <= n; i++){
      if(tvec[i] != 0){
         return false;
      }
   }
   return true;
}
int main() {
   int n = 3, m = 2;
   vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
   cout<< solve(n, m, stacks);
   return 0;
}

Input

3, 2, {{2, 1, 3}, {2, 1, 3}}

Output

1

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!