두 개의 문자 스택을 지울 수 있는지 확인하는 C++ 프로그램-C++-php.cn

두 개의 문자 스택을 지울 수 있는지 확인하는 C++ 프로그램

PHPz

풀어 주다： 2023-09-04 14:01:06

앞으로

1142명이 탐색했습니다.

두 개의 문자 스택을 지울 수 있는지 확인하는 C++ 프로그램

2n개의 문자가 있다고 가정하고 각 문자에는 1에서 n 사이의 정수가 적혀 있습니다. 같은 숫자가 쓰여진 두 글자가 있습니다. 이 글자들은 m개의 더미로 나누어져 있고, i번째 더미에는 stack[i] 글자가 있습니다. 우리의 임무는 다음과 같은 방법으로 모든 더미를 비우는 것입니다:

두 개의 더미를 선택하고 두 더미에서 맨 위 문자를 제거해야 합니다.
제거하는 문자의 숫자는 동일해야 합니다.

이 방법으로 m-힙을 지울 수 있으면 true를 인쇄하고, 그렇지 않으면 false를 반환합니다.

따라서 입력이 n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}이면 출력은 true가 됩니다.

두 개의 더미가 있고, 각 더미의 문자에는 각각 2, 1, 3이라는 숫자가 적혀 있습니다. 따라서 우리는 주어진 방법으로 두 더미에서 문자를 제거하고 비울 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

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

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. -

#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;
}

로그인 후 복사