C++ program to check if two letter stacks can be cleared

Suppose there are 2n letters, each letter has an integer between 1 and n written on it. There are two letters with the same number written on them. These letters are divided into m piles, and there is stack[i] letter on the i-th pile. Our task is to empty all the piles in the following way:

• We have to select any two piles and remove the top letter from both piles.

• The letters we remove must have the same number.

If we can clear the m-heap in this way, print true, otherwise return false.

So if the input is n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}, then the output will be true.

There are two piles, and the numbers 2, 1, and 3 are written on the letters in each pile. So we can remove letters from both piles and empty them in the given manner.

To solve this problem, we will follow the following steps:

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

Example

Let us see the following implementation for better understanding-

#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

The above is the detailed content of C++ program to check if two letter stacks can be cleared. For more information, please follow other related articles on the PHP Chinese website!