Maison > Article > développement back-end > 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
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; }
3, 2, {{2, 1, 3}, {2, 1, 3}}
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!